ЛОШ2014: 18 июня 2014. На РОИ я, видимо, пройду и так...

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

• ADD: положить в черный ящик элемент;
• GET: увеличить значение i на 1 и выдать i - ый минимальный из содержащихся в черном ящике элементов. Напомним, что i - ым минимальным называется число, стоящее на i - ом месте после сортировки элементов черного ящика в порядке неубывания.

Рассмотрим возможную последовательность из 11 запросов:

№	Запрос	i	Содержимое черного ящика после запроса (элементы расположены в порядке неубывания)	Ответ
1	ADD (3)	0	3
2	GET	1	3	3
3	ADD (1)	1	1, 3
4	GET	2	1, 3	3
5	ADD (-4)	2	-4, 1, 3
6	ADD (2)	2	-4, 1, 2, 3
7	ADD (8)	2	-4, 1, 2, 3, 8
8	ADD (-1000)	2	-1000, -4, 1, 2, 3, 8
9	GET	3	-1000, -4, 1, 2, 3, 8	1
10	GET	4	-1000, -4, 1, 2, 3, 8	2
11	ADD (2)	4	-1000, -4, 1, 2, 2, 3, 8

Требуется разработать эффективный алгоритм, обрабатывающий заданную последовательность запросов. Максимальное допустимое количество запросов ADD и GET — по 30000 каждого типа. Последовательность запросов будем задавать двумя наборами чисел:

1. Последовательностью включаемых в черный ящик элементов A (1), A (2), ... A ( M ) . Значения A — целые числа, не превосходящие по абсолютной величине 2 000 000 000, 1 ≤ M ≤ 30000 . Для примера 1 имеем A =(3, 1, -4, 2, 8, -1000, 2).
2. Последовательностью u (1), u (2), ... u ( N ) , задающей количество содержащихся в черном ящике элементов в момент выполнения первой, второй, ..., N - ой команды GET. Для примера 1 имеем 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 )) .