EduBrick

B. K-й максимум

1500 мс · 64 МБ · всё или ничего

Реализуйте структуру, которая умеет добавлять элемент, удалять элемент и находить kk-й по величине среди хранящихся — считая от наибольшего.

Гарантируется, что равные ключи в структуру не кладут, несуществующие не удаляют, а при запросе kk-го максимума он существует.

Формат ввода

В первой строке — число команд nn (1≤n≤1051 \le n \le 10^5). В следующих nn строках — команды: 1 k добавить ключ kk, -1 k удалить ключ kk, 0 k вывести kk-й максимум. Ключи целые, по модулю не больше 10910^9.

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

На каждую команду вида 0 выведите kk-й максимум в отдельной строке.

Примеры

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