Черный Ящик
Черный Ящик представляет собой примитивную базу даных. Он может хранить массив целых чисел, а также имеет специальную переменную i. В начальный момент Черный Ящик пустой, переменная i равна 0. Черный Ящик обрабатывает последовательность команд (транзакций). Существует два типа транзакций:
ADD(x): добавить элемент x в Черный Ящик;
GET: увеличить i на 1 и вывести i-ый минимальный элемент среди всех чисел, находящихся в Черном Ящике.
Помните, что i-ый минимальный элемент находится на i-ом месте после того как все элементы Черного Ящика будут отсортированы в неубывающем порядке.
Рассмотрим работу черного ящика на примере:
Необходимо разработать эффективный алгоритм выполнения заданной последовательности транзакций. Максимальное количество транзакций ADD и GET равно 30000 (каждого типа).
Опишем последовательность транзакций двумя целочисленными массивами:
1. A(1), A(2), ..., A(m): последовательность элементов, которая будет добавляться в Черный Ящик. Элементами являются целые числа, по модулю не большие 2 000 000 000, m ≤ 30000. Для выше описанного примера 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) отсортированы в неубывающем порядке, n ≤ m, а для каждого p (1 ≤ p ≤ n) имеет место неравенство p ≤ u(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). Все числа разделены пробелами и (или) символом перевода на новую строку.
Выходные данные
Вывести ответы Черного Ящика на последовательность выполненных транзакций. Каждое число должно выводиться в отдельной строке.