Черный ящик организован наподобие примитивной базы данных. Он может хранить набор целых чисел и имеет выделенную переменную 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 )) .

Как известно, Нью-Йорк большой город. На главной улице находится N небоскребов в ряд, в i - м небоскребе есть A _i свободных офисов. Недавно в городе образовались M компаний. Каждой из них конечно нужны офисы, но управляющие i - й компании хотят получить по офису в каждом небоскребе с L _i по R _i . Напишите программу, которая вычислит, какое максимальное количество компаний может получить офисы на главной улице Нью-Йорка в соответствии с их требованиями.

Скоро начнётся сезон роста бамбука. Скупщики бамбука принимают любое количество бамбука каждый день ровно в полдень. Однако цена бамбука каждый день меняется. Нам удалось узнать, по какой цене скупщики будут принимать бамбук. Кроме того, мы точно знаем, на сколько метров вырастает бамбук за каждые сутки (эта величина тоже меняется). В любой день можно либо срезать весь бамбук целиком и продать его, либо оставить бамбук расти дальше. После срезания бамбук продолжает расти. Требуется определить, какую максимальную прибыль от продажи бамбука можно получить. В полдень нулевого дня (начало сезона роста бамбука) длина бамбука равна 0. Сезон роста бамбука длится ровно N суток.

Поблизости от столицы Флатландии одна компания решила построить коттеджный поселок. Строительная компания, которая занимается возведением коттеджей, решила раскрасить некоторые коттеджи в розовый цвет, а остальные - в голубой. Но они не могут решить какой коттедж раскрасить в какой цвет.

Директор компании утверждает, что раскраска симпатичная, если есть хотя бы один розовый коттедж, хотя бы один голубой коттедж, и можно провести такую прямую, что все розовые коттеджи окажутся с одной стороны от нее, я голубые - с другой стороны (при этом на самой прямой коттеджей быть не должно). На это главный дизайнер возразил, что есть несколько способов сделать симпатичную раскраску.

Помогите им определить, сколько существует различных симпатичных раскрасок.