В компьютерной игре есть $$$n$$$ башен, высота $$$i$$$-й башни равна $$$a_i$$$ метров. Определим расстояние между двумя башнями с индексами $$$i$$$ и $$$j$$$ как $$$|i - j|$$$. Разрешается прыгнуть с $$$i$$$-й башни на $$$j$$$-ю башню тогда и только тогда, когда не существует такого индекса $$$1 \le k \le n$$$, такого, что расстояние от $$$i$$$-й до $$$j$$$-й башни не меньше расстояния от $$$i$$$-й башни до $$$k$$$-й башни, и $$$k$$$-я башня имеет большую высоту, чем $$$j$$$-я. Башня $$$j$$$ достижима из башни $$$i$$$ если существует последовательность корректных прыжков, которая начинается в $$$i$$$-й башне и заканчивается в $$$j$$$-й. Посчитайте для каждой башни количество достижимых из неё башен, включая её саму.
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 500\,000$$$) — количество башен.
Вторая строка входных данных содержит $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_n \le 10^9$$$) — высоты башен.
Выведите $$$n$$$ чисел, $$$i$$$-е из которых должно быть равным количеству башен, достижимых из $$$i$$$-й башни.
5 7 6 3 4 10
2 3 4 2 1
7 1 1 1 2 2 1 1
5 5 3 2 2 3 4
В первом примере с $$$1$$$-й башни можно прыгнуть на башни $$$1$$$ и $$$5$$$. Любая другая башня имеет меньшую высоту, чем башня $$$1$$$, поэтому туда нельзя прыгнуть (в качестве $$$k$$$ можно выбрать $$$1$$$). Множество достижимых из $$$1$$$-й башни также состоит из башен $$$1$$$ и $$$5$$$. Со второй башни можно прыгнуть на башни $$$1$$$, $$$2$$$, и $$$5$$$, они же являются множеством достижимых. С третьей башни можно прыгнуть на башни $$$2$$$, $$$3$$$, $$$5$$$. Однако, башня $$$1$$$ также является достижимой, поскольку можно сделать два прыжка: $$$3 \to 2 \to 1$$$. Таким образом, получается $$$4$$$ достижимые башни. С $$$4$$$-й башни можно прыгнуть на башни $$$4$$$ и $$$5$$$, они же являются единственными достижимыми. Из $$$5$$$-й башни достижима только она сама.
Во втором примере из $$$1$$$-й и из $$$2$$$-й башни достижимы башни $$$1, 2, 3, 4, 5$$$. Из $$$3$$$-й башни достижимы башни $$$3, 4, 5$$$. Из $$$4$$$-й и $$$5$$$-й башни достижимы башни $$$4, 5$$$. Из $$$6$$$-й башни достижимы башни $$$4, 5, 6$$$. Из $$$7$$$-й башни достижимы башни $$$4, 5, 6, 7$$$.
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
Обозначим за $$$C$$$ высоту самой высокой башни.
Группа | Баллы | Ограничения | Необходимые группы | ||
n | C | Дополнительно | |||
0 | 0 | Тесты из условия | |||
1 | 18 | $$$n \le 100$$$ | $$$C \le 10^9$$$ | 0 | |
2 | 11 | $$$n \le 2000$$$ | $$$C \le 10^9$$$ | Все $$$a_i$$$ различны | |
3 | 9 | $$$n \le 200\,000$$$ | $$$C \le 2$$$ | ||
4 | 16 | $$$n \le 200\,000$$$ | $$$C \le 3$$$ | 3 | |
5 | 19 | $$$n \le 10\,000$$$ | $$$C \le 10^9$$$ | 0–2 | |
6 | 27 | $$$n \le 500\,000$$$ | $$$C \le 10^9$$$ | Offline-проверка | 0–5 |