eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Персистентная приоритетная очередь

Персистентная приоритетная очередь

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Реализуйте персистентную приоритетную очередь.

Входные данные

Первая строка содержит количество действий n (1n200000). Строка номер i + 1 содержит описание действия i:

  • x m - добавить в структуру с номером x (0x < i) число m (0 < m100000);

  • x 0 - удалить максимальный элемент со структуры под номером x (0x < i). Гарантируется, что приоритетная очередь x не пустая.

В результате действия i, описанной в строке i + 1, образуется новая структура с номером i. Сначала имеется пустой стек с номером ноль.

Выходные данные

Для каждой операции удаления выведите удаляемый элемент в отдельной строке.

Пример

Входные данные #1
6
0 1
1 2
2 3
3 0
4 0
5 0
Выходные данные #1
3
2
1
Автор Александр Цицюра