Республиканская олимпиада по информатике 2009 год

Задача B. Фокус

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

2 секунды

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

256 мегабайт

Помните про фокус с мухами, который изобрел Баха? Жома решил посоревноваться с ним и придумал свой фокус! У Жомы есть ящик. Он может запускать туда муху или выпускать. Также, он как хороший дрессировщик знает возраст каждой мухи в минутах с момента ее рождения. А фокус заключается вот в чем: в любой момент он может назвать возраст $K$-й по старшинству мухи, которая находится в ящике среди мух с возрастом от $A$ до $B$ включительно. Попробуйте и вы сделать этот фокус!

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

Первая строка входного файла содержит число $N$ — общее количество событий ($1 \le N \le 2 \cdot 10^5$). Далее следует $N$ строк, каждая из которых описывает одно из событий:

• $+ X$ — в ящик впустили муху с возрастом $X$;
• $- X$ — из ящика выпустили муху с возрастом $X$;
• $? K A B$ — у фокусника спросили возраст $K$-й по старшинству мухи в ящике среди мух с возрастом от $A$ до $B$ включительно ($1 \le K \le 10^5$, $A \le B$);

Возраст мухи ($X$, $A$, $B$) — целое число от $1$ до $10^5$.

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

Выходной файл должен содержать такое же количество строк, сколько запросов возраста было во входном файле. Для каждого такого запроса нужно вывести строку, содержащую соответствующее число — ответ на запрос. При этом, если при количество мух с возрастом от $A$ до $B$ в ящике меньше $K$, то нужно вывести $0$.

Пример:

Вход

8
+ 2
+ 3
+ 2
? 2 2 3
- 2
? 2 2 3
- 2
? 2 2 3

Ответ

2
3
0