Автоботы отважились на штурм базы десептиконов. Из-за эффекта внезапности множество десептиконов полегло на месте, а остальные начали судорожно прятаться в бункеры, которые начали закрываться. Оптимус Прайм хочет добить как можно больше десептиконов. Для этого он решил использовать новую разработку автоботов — бомбу «Антибункер».

Принцип работы бомбы заключается в том, что ее можно кинуть внутрь бункера, а когда тот закроется — взорвать, и тогда она убьет всех, кто был внутри. Единственное ее неудобство заключается в том, что взрывается она неавтоматически. То есть Оптимусу, после того, как он кинет бомбу, придется ждать закрытия бункера, чтобы взорвать всех внутри, и лишь потом он сможет поехать дальше.

Оптимус собирается проехать мимо каждого бункера ровно один раз, посетив их в порядке возрастания номеров. К счастью, он знает, на какой минуте закроется каждый из бункеров, а также количество десептиконов в каждом из бункеров. Между бункерами Оптимус перемещается очень быстро — перемещение между любой парой бункеров занимает у него ровно одну минуту. Если он проехал бункер, он уже не сможет вернуться обратно.

Оптимус Прайм просит вас помочь ему рассчитать, какое наибольшее количество врагов он сможет убить, и в какие бункеры нужно бросить бомбу для этого.

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

В одном большом городе очень много достопримечательностей и в него регулярно приезжают толпы туристов. Но просто приезжать в город неинтересно, и туристы любят осматривать достопримечательности. Все туристы — занятые люди и осматривать две достопримечательности одного и того же типа не собираются. Например, никто не пойдёт в два музея, ведь, чтобы сказать, что ты был в музее, достаточно сходить только в один. Все n достопримечательностей расположены вдоль главной улицы города. Каждая достопримечательность имеет свой тип — музей, театр, памятник... Каждый приезжающий турист заказывает в турагенстве экскурсию. Экскурсия представляет из себя проезд по каким-то достопримечательностям, стоящим подряд. Так как туристы живут в разных частях города, то не всем им удобно добираться до главной улицы. Поэтому, для i -го туриста есть границы [ l _i ; r _i ] — отрезок, в который должны попасть начало и конец экскурсии, ведь ему надо не только приехать на неё, ну и уехать потом домой. Каждый турист хочет осмотреть как можно больше достопримечательностей, но при этом он не будет смотреть более одной достопримечательности одного типа. Помогите турагенству подобрать каждому туристу подходящую ему экскурсию.

Петя пишет программы для бирж. Он занимается разработкой различных финансовых инструментов, его последний проект связан с анализом возможности арбитража с использованием исторических данных о котировках существенно волатильной акции.

Идея анализа состоит в следующем: по заданным котировкам акции в течение n последовательных дней, требуется выбрать подпоследовательность котировок, которая удовлетворяет следующему свойству: любые две соседние котировки в выбранной подпоследовательности должны отличаться не менее чем на k . Например, если котировки равны, соответственно, 1014, 1024, 1034, 1045, 1030, 998 и k = 15 , то подпоследовательность котировок 1014, 1034, 998 является допустимой. Выбранная подпоследовательность должны быть как можно длиннее. Так, в приведенном примере выбранная последовательность не является оптимальной, подпоследовательность 1014, 1045, 1030, 998 лучше.

По заданной последовательности котировок, найдите ее длиннейшую допустимую подпоследовательность.