B. Шаг вперёд, три шага назад
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На занятии по программированию преподаватель предложил всем студентам для начала решить одну не очень сложную задачу. Конечно же, Фалалей захотел получить решение этой задачи с помощью новой версии большой языковой модели $$$BreadTHin$$$. Преподаватель, разумеется, говорил, что будет засчитывать только полностью самостоятельные решения, но Фалалей уверен, что решение $$$BreadTHin$$$ преподаватель не отличит от «человеческого».

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

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

Опишем происходящее более формально.

Пусть Фалалей только что отправил решение $$$\#(j-1)$$$, оно набрало $$$x_{j-1}$$$ баллов, и это больше, чем любое решение с меньшим номером. Будем называть это решение «лучшей попыткой».

Каждый раз, получая «лучшую попытку», Фалалей сразу же пытается её ещё улучшить и повторяет описанные ниже действия.

Фалалей просит $$$BreadTHin$$$ улучшить решение $$$\#(j-1)$$$, получает решение $$$\#j$$$, отправляет его на проверку, и это решение набирает $$$x_j$$$ баллов.

Если $$$x_{j} \le x_{j-1}$$$, Фалалей назовёт это решение «более плохим».

Фалалей готов сделать до трёх попыток улучшения «более плохого» решения.

Если в какой-либо из попыток $$$\#(j+k)$$$ $$$(k = 0, 1, 2, 3)$$$ Фалалей получит решение, набирающее $$$x_{j+k} \gt x_{j-1}$$$ баллов, то он назовёт это решение новой «лучшей попыткой» (и далее будет пытаться улучшать уже его).

Если же в ходе этих попыток получить новую «лучшую попытку» не удастся, Фалалей обратится к $$$BreadTHin$$$ с запросом на новое улучшение имеющейся «лучшей попытки» — решения $$$\#(j-1)$$$.

Более того, если в первой или второй попытке Фалалей получит решение, набирающее ещё меньше баллов, чем «более плохое» решение ($$$x_{j+k} \lt x_{j}, \, k = 1, 2$$$), то он обратится к $$$BreadTHin$$$ с запросом на новое улучшение решения $$$\#(j-1)$$$ (имеющейся «лучшей попытки») — сразу после этой попытки.

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

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

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

Далее в каждой строке содержится по одному целому числу $$$b_j$$$ $$$(0 \le b_j \le 10^6, \, j = 1, 2, \ldots, n)$$$, $$$b_j$$$ — количество баллов, набранное за решение $$$\#j$$$.

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

В первой строке выведите целое число $$$m$$$ — количество решений, к которым возвращался Фалалей.

Далее в каждой из $$$m$$$ строк выведите по два числа: номер решения, к которому возвращался Фалалей, и через пробел — количество раз, которое он к нему возвращался.

Выводите решения по порядку их номеров.

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

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

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

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

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

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

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
11 (до 5)$$$n \le 5, \, b_j \le 10$$$нетполная
22 (до 20)$$$n \le 20, \, b_j \le 3$$$1полная
32 (до 10)$$$ b_j \le 1$$$нетполная
40 (65)любые допустимые значения1, 2, 3первая ошибка

Примеры
Входные данные
22
23
28
17
22
19
25
23
16
25
27
27
22
24
47
32
35
28
24
31
30
52
48
Выходные данные
2
2 3
14 1
Входные данные
5
72
57
64
68
62
Выходные данные
0
Примечание

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

В первом примере происходит следующее.

Решение $$$\#1$$$ набирает 23 балла и сначала является (первой и единственной) лучшей попыткой. Однако первое же улучшение его — решение $$$\#2$$$ — даёт 28 баллов, и сразу же становится лучшей попыткой.

Теперь Фалалей запрашивает улучшение решения $$$\#2$$$. Полученное решение $$$\#3$$$ хуже, оно даёт только 17 баллов. Однако Фалалей попытается его улучшить. Первая такая попытка принесёт 22 балла, следующая — 19 баллов, и ещё одна — 25 баллов. Поскольку Фалалей ограничивается тремя попытками улучшить более плохое решение, то после этой попытки (решения $$$\#6$$$) он снова запросит улучшение решения $$$\#2$$$, и это будет первое возвращение к этому решению.

Решение $$$\#7$$$, являющееся улучшением решения $$$\#2$$$, даёт 23 балла. Фалалей попытается улучшить это решение, но уже следующая попытка (решение $$$\#8$$$) даст только 16 баллов, и Фалалей вновь запросит улучшение решения $$$\#2$$$. Это будет второе возвращение к этому решению.

Решение $$$\#9$$$, полученное в результате улучшения решения $$$\#2$$$, даст 25 баллов, следующие две попытки улучшить уже решение $$$\#9$$$ дадут по 27 баллов, а третья попытка — 22 балла. Так что к решению $$$\#2$$$ Фвлалаей вернётся в третий раз.

Решение $$$\#13$$$ даст 24 балла, но первая же попытка улучшить его станет лучшей попыткой из всех сделанных: решение $$$\#14$$$ даст 47 баллов. Теперь Фалалей попробует улучшать уже его.

Первое улучшение решения $$$\#14$$$ — решение $$$\#15$$$ даст 32 балла. Как обычно, Фалалей попробует улучшить его. Первая из таких попыток даст 35 баллов, а вторая — 28, что меньше даже 32. Поэтому Фалалей вернётся к решению $$$\#14$$$, и это будет первое такое возвращение.

Решение $$$\#18$$$ – новая попытка улучшить решение $$$\#14$$$ — даст 24 балла. Следующие две попытки улучшить решение $$$\#18$$$ дадут 31 и 30 баллов соответственно, а вот третья попытка (решение $$$\#21$$$) даст 52 балла и станет новой лучшей попыткой.

Фалалей запросит улучшение решения $$$\#21$$$, получит решение $$$\#22$$$, набирающее 48 баллов. На этом история запросов заканчивается, поэтому в качестве ответа мы выведем 2 решения: $$$\#2$$$ и $$$\#14$$$. К решению $$$\#22$$$ Фалалей возвращался трижды, а к решению $$$\#14$$$ — единожды.

Во втором примере Фалалей начинает с решения, набирающего 72 балла. Попытка улучшить его приводит к решению, набирающему 57 баллов. Следующие три попытки улучшения более плохого решения получают больше, чем 57 баллов каждая, но не более 72. Если бы он продолжал попытки, он вернулся бы решению, набравшему 72 балла. Но история запросов заканчивается, поэтому возвращения не происходит.