Областная олимпиада по информатике, 2009-2010 учебный год

Задача F. Агентство

Ограничение по времени:

2 sec.

Ограничение по памяти:

64MB

Вам поручили работу с базой данных агенства по недвижимости. В базу постоянно вносятся сведения о новых квартирах: их стоимость и удобство, оцененные в целых числах от 1 до 109, и удаляются сведения о проданных квартирах. В произвольный момент времени требуется узнавать номер квартиры с наибольшим удобством среди квартир между і-й и ј-й по увеличению стоимости включительно.

Формат входного файла

Первая строка входного файла содержит число N – количество операций с базой данных (1≤ N ≤ 300000). Следующие N строк содержат описание операций в следующем формате: “+ А В ” – добавить в базу квартиру стоимостью А и удобством В ( 1≤ А, В ≤ 109, все А различны, все В различны); “- Х”- удалить квартиру номер Х (Х ≥ 1, гарантируется, что квартира с номером Х есть в базе); “# і ј”- вывести номер квартиры с наибольшим удобством среди квартир между і-й и ј-й по увеличению стоимости включительно (1≤ і ≤ ј, гарантируется, что количество квартир в базе не меньше ј. Квартиры нумеруются целыми числами с 1 в порядке добавления в базу. Числа и знаки в строках разделены пробелами.

Формат выходного файла

В выходной файл на каждый запрос вида “# і ј” выведите одно целое число – номер соответствующей квартиры.

Пример:

Вход:

7
+ 10 1
+11 4
# 1 2
- 2
+ 13 2
# 1 2

 Ответ:

2
3