e-olymp
Задачи

Черный Ящик

Черный Ящик

Черный Ящик представляет собой примитивную базу даных. Он может хранить массив целых чисел, а также имеет специальную переменную i. В начальный момент Черный Ящик пустой, переменная i равна 0. Черный Ящик обрабатывает последовательность команд (транзакций). Существует два типа транзакций:

ADD(x): добавить элемент x в Черный Ящик;

GET: увеличить i на 1 и вывести i-ый минимальный элемент среди всех чисел, находящихся в Черном Ящике.

Помните, что i-ый минимальный элемент находится на i-ом месте после того как все элементы Черного Ящика будут отсортированы в неубывающем порядке.

Рассмотрим работу черного ящика на примере:

Nтранзакцияiсодержимое Черного Ящика после транзакцииОтвет
1ADD(3)0 3
2GET1 33
3ADD(1)1 1, 3
4GET2 1, 33
5ADD(-4)2 -4, 1, 3
6ADD(2)2 -4, 1, 2, 3
7ADD(8)2 -4, 1, 2, 3, 8
8ADD(-1000)2 -1000, -4, 1, 2, 3, 8
9GET3 -1000, -4, 1, 2, 3, 81
10GET4 -1000, -4, 1, 2, 3, 82
11ADD(2)4 -1000, -4, 1, 2, 2, 3, 8

Необходимо разработать эффективный алгоритм выполнения заданной последовательности транзакций. Максимальное количество транзакций ADD и GET равно 30000 (каждого типа).

Опишем последовательность транзакций двумя целочисленными массивами:

1. A(1), A(2), ..., A(m): последовательность элементов, которая будет добавляться в Черный Ящик. Элементами являются целые числа, по модулю не большие 2 000 000 000, m30000. Для выше описанного примера A = (3, 1, -4, 2, 8, -1000, 2).

2.u(1), u(2), ..., u(n): последовательность указывает на количество элементов в Черном Ящике в момент выполнения первой, второй, ... n-ой транзакции GET. Для выше описанного примера u = (1, 2, 6, 6).

Работа Черного Ящика предполагает, что числа в последовательности u(1), u(2), ..., u(n) отсортированы в неубывающем порядке, nm, а для каждого p (1pn) имеет место неравенство pu(p) ≤ m. Это следует из того, что для p-го элемента последовательности u мы выполняем GET транзакцию, которая выводит p-ый минимальный элемент из набора чисел A(1), A(2), ..., A(u(p)).

Входные данные

Состоит из следующего набора чисел: m, n, A(1), A(2), ..., A(m), u(1), u(2), ..., u(n). Все числа разделены пробелами и (или) символом перевода на новую строку.

Выходные данные

Вывести ответы Черного Ящика на последовательность выполненных транзакций. Каждое число должно выводиться в отдельной строке.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
Выходные данные
3
3
1
2