В компьютерной игре есть
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
|