Кеша участвует в соревнованиях по программированию. Его друг Прохор не особенно интересуется алгоритмическим программированием, поэтому просто наблюдает за соревнованиями со стороны: просматривает приходящие уведомления и таблицу результатов.
По правилам соревнований участники упорядочиваются по количеству решенных задач; участник, решивший наибольшее количество задач, занимает первое место и т.д. При равном количестве решенных задач используются дополнительные критерии, но Прохор не хочет в них разбираться. Ему достаточно знать диапазон мест, занятых участниками с таким же количеством задач, которое в данный момент решил Кеша.
Каждый раз, когда какой-либо участник решает какую-либо задачу, приходит уведомление об этом. Для упрощения будем считать, что уведомление содержит только номер участника. Кеша получил номер участника $$$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 = 0$$$ выведите два целых числа — наиболее высокое и наименее высокое места участников, решивших в этот момент столько же задач, сколько и Кеша.
Разделяйте числа пробелом или переводом строки.
В первой и второй подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
Для решения второй подзадачи требуется, чтобы программа верно решала первую подзадачу.
В третьей подзадаче баллы начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.
Также для третьей подзадачи требуется, чтобы программа верно решала предшествующие подзадачи.
Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 10) | $$$\max\limits_{j=1}^{n}{q_j} \le 10, \, n \le 100$$$ | нет | полная |
| 2 | 2 (до 30) | $$$\max\limits_{j=1}^{n}{q_j}, \, n \le 1000$$$ | 1 | полная |
| 3 | 0 (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
Поясним приведённый пример.
| Name |
|---|


