В компьютерной игре есть
n
башен, высота
i
-й башни равна
ai
метров. Определим расстояние между двумя башнями с индексами
i
и
j
как
|i−j|
. Разрешается прыгнуть с
i
-й башни на
j
-ю башню тогда и только тогда, когда не существует такого индекса 1 <=
k
<=
n
, такого, что расстояние от
i
-й до
j
-й башни не меньше расстояния от
i
-й башни до
k
-й башни, и
k
-я башня имеет большую высоту, чем
j
-я. Башня
j
достижима из башни
i
если существует последовательность корректных прыжков, которая начинается в
i
-й башне и заканчивается в
j
-й. Посчитайте для каждой башни количество достижимых из неё башен, включая её саму.
Входные данные
Первая строка входных данных содержит одно целое число n
(1 <= n
<= 500000) - количество башен.
Вторая строка входных данных содержит n
чисел a1
, a2
, ..., an
(1 <= an
<= 109) - высоты башен.
Выходные данные
Выведите
n
чисел,
i
-е из которых должно быть равным количеству башен, достижимых из
i
-й башни.
Примечание
В первом примере с 1-й башни можно прыгнуть на башни 1 и 5. Любая другая башня имеет меньшую высоту, чем башня 1, поэтому туда нельзя прыгнуть (в качестве k
можно выбрать 1). Множество достижимых из 1-й башни также состоит из башен 1 и 5. Со второй башни можно прыгнуть на башни 1, 2, и 5, они же являются множеством достижимых. С третьей башни можно прыгнуть на башни 2, 3, 5. Однако, башня 1 также является достижимой, поскольку можно сделать два прыжка: 3→2→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.
Примеры
№ |
Входные данные |
Выходные данные |
1 |
5
7 6 3 4 10
|
2 3 4 2 1
|
2 |
7
1 1 1 2 2 1 1
|
5 5 3 2 2 3 4
|