Башни 2.0
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В компьютерной игре есть $$$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$$$ высоту самой высокой башни.

ГруппаБаллыОграниченияНеобходимые группы
nCДополнительно
00Тесты из условия
118$$$n \le 100$$$$$$C \le 10^9$$$0
211$$$n \le 2000$$$$$$C \le 10^9$$$Все $$$a_i$$$ различны
39$$$n \le 200\,000$$$$$$C \le 2$$$
416$$$n \le 200\,000$$$$$$C \le 3$$$3
519$$$n \le 10\,000$$$$$$C \le 10^9$$$0–2
627$$$n \le 500\,000$$$$$$C \le 10^9$$$Offline-проверка0–5