D. Диапазоны
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кеша участвует в соревнованиях по программированию. Его друг Прохор не особенно интересуется алгоритмическим программированием, поэтому просто наблюдает за соревнованиями со стороны: просматривает приходящие уведомления и таблицу результатов.

По правилам соревнований участники упорядочиваются по количеству решенных задач; участник, решивший наибольшее количество задач, занимает первое место и т.д. При равном количестве решенных задач используются дополнительные критерии, но Прохор не хочет в них разбираться. Ему достаточно знать диапазон мест, занятых участниками с таким же количеством задач, которое в данный момент решил Кеша.

Каждый раз, когда какой-либо участник решает какую-либо задачу, приходит уведомление об этом. Для упрощения будем считать, что уведомление содержит только номер участника. Кеша получил номер участника $$$1$$$.

В некоторые моменты Прохор интересуется, в каком диапазоне мест находится сейчас Кеша. Это значит, что он хочет узнать два числа:

  • наиболее высокое место (минимальное значение), которое занимает участник, решивший столько же задач, сколько и Кеша;
  • наименее высокое место (максимальное значение), которое занимает участник, решивший столько же задач, сколько и Кеша.

Ваша задача — получить ответы на вопросы Прохора.

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

В первой строке содержится целое число $$$n$$$ $$$(2 \le n \le 3 \cdot 10^5)$$$ — суммарное количество уведомлений и запросов Прохора.

Во второй строке содержится $$$n$$$ целых чисел $$$q_j$$$ $$$(0 \le q_j \le 10^6, \, j = 1, 2, \ldots, n)$$$ через пробел:

  • Если $$$q_j \gt 0$$$ — это номер участника, сдавшего очередную задачу. Напомним, что у Кеши номер $$$1$$$.
  • Если же $$$q_j = 0$$$, то это запрос Прохора: нужно вывести наиболее высокое и наименее высокое места участников, решивших столько же задач, сколько и Кеша.

Гарантируется, что:

  • во входных данных имеется по крайней мере одно уведомление и по крайней мере один запрос.
  • Прохор впервые заинтересуется диапазоном не ранее, чем Кеша решит хотя бы одну задачу.
Выходные данные

Для каждого $$$q_j = 0$$$ выведите два целых числа — наиболее высокое и наименее высокое места участников, решивших в этот момент столько же задач, сколько и Кеша.

Разделяйте числа пробелом или переводом строки.

Система оценки

В первой и второй подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

Для решения второй подзадачи требуется, чтобы программа верно решала первую подзадачу.

В третьей подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

Также для третьей подзадачи требуется, чтобы программа верно решала предшествующие подзадачи.

Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
12 (до 10)$$$\max\limits_{j=1}^{n}{q_j} \le 10, \, n \le 100$$$нетполная
22 (до 30)$$$\max\limits_{j=1}^{n}{q_j}, \, n \le 1000$$$1полная
30 (60)любые допустимые значения1, 2первая ошибка

Пример
Входные данные
25
2 7 1 2 0 3 7 1 0 2 2 0 5 7 0 5 0 3 1
0 1 0 2 7 0
Выходные данные
2 3
1 3
2 3
3 3
3 4
2 3
1 2
2 3
Примечание

Поясним приведённый пример.

  • К первому запросу Прохора:
    • участник $$$2$$$ занимает место $$$1$$$ с двумя решенными задачами;
    • участники $$$7$$$ и $$$1$$$ (Кеша) занимают места со $$$2$$$ по $$$3$$$ с одной решенной задачей.
  • Ко второму запросу Прохора:
    • участники $$$2$$$, $$$7$$$ и $$$1$$$ (Кеша) занимают места с $$$1$$$ по $$$3$$$ с двумя решенными задачами;
    • участник $$$3$$$ — место $$$4$$$ с одной задачей.
  • К третьему запросу Прохора:
    • участник $$$2$$$ занимает место $$$1$$$ с четырьмя решенными задачами;
    • участники $$$7$$$ и $$$1$$$ (Кеша) занимают места со $$$2$$$ по $$$3$$$ с двумя решенными задачами;
    • участник $$$3$$$ — место $$$4$$$ с одной задачей.
  • К четвертому запросу Прохора:
    • участник $$$2$$$ занимает место $$$1$$$ с четырьмя решенными задачами;
    • участник $$$7$$$ занимает место $$$2$$$ с тремя решенными задачами;
    • участник $$$1$$$ (Кеша) занимает место $$$3$$$ с двумя решенными задачами;
    • участники $$$3$$$ и $$$5$$$ — места с $$$4$$$ по $$$5$$$ с одной задачей.
  • К пятому запросу Прохора:
    • участник $$$2$$$ занимает место $$$1$$$ с четырьмя решенными задачами;
    • участник $$$7$$$ занимает место $$$2$$$ с тремя решенными задачами;
    • участники $$$1$$$ (Кеша) и $$$5$$$ занимают места с $$$3$$$ по $$$4$$$ с двумя решенными задачами;
    • участник $$$3$$$ — место $$$5$$$ с одной задачей.
  • К шестому запросу Прохора:
    • участник $$$2$$$ занимает место $$$1$$$ с четырьмя решенными задачами;
    • участники $$$7$$$ и $$$1$$$ (Кеша) занимают места со $$$2$$$ по $$$3$$$ с тремя решенными задачами;
    • участники $$$5$$$ и $$$3$$$ занимают места с $$$4$$$ по $$$5$$$ с двумя решенными задачами.
  • К седьмому запросу Прохора:
    • участники $$$2$$$ и $$$1$$$ (Кеша) занимают места с $$$1$$$ по $$$2$$$ с четырьмя решенными задачами;
    • участник $$$7$$$ занимает место $$$3$$$ с тремя решенными задачами;
    • участники $$$5$$$ и $$$3$$$ занимают места с $$$4$$$ по $$$5$$$ с двумя решенными задачами.
  • К восьмому запросу Прохора:
    • участник $$$2$$$ занимает место $$$1$$$ с пятью решенными задачами;
    • участники $$$7$$$ и $$$1$$$ (Кеша) занимают места со $$$2$$$ по $$$3$$$ с четырьмя решенными задачами;
    • участники $$$5$$$ и $$$3$$$ занимают места с $$$4$$$ по $$$5$$$ с двумя решенными задачами.