Задача 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