EduBrick

D. K-й по возрастанию

2500 мс · 256 МБ · всё или ничего

Мультимножество целых чисел, изначально пустое. Обрабатывайте запросы:

  • + x — добавить число xx;
  • - x — удалить одно вхождение числа xx (оно есть);
  • ? k — вывести kk-е по возрастанию число (оно есть).

Формат ввода

В первой строке — число запросов qq (1≤q≤2⋅1051 \le q \le 2 \cdot 10^5). В следующих qq строках — запросы; 1≤x≤1061 \le x \le 10^6, kk не превосходит текущего размера мультимножества.

Формат вывода

На каждый запрос ? выведите искомое число.

Примеры

ввод
7
+ 5
+ 3
+ 5
? 1
? 2
- 5
? 2
вывод
3
5
5
ввод
2
+ 1000000
? 1
вывод
1000000
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.