The computer game has
n towers, the height
ith tower is
ai meters . Define the distance between two towers with indices
i and
j as
|i−j|. It is allowed to jump from
ith tower to
jth tower if and only if no such index exists 1 <=
k <=
n such that the distance from the
ith to the
jth tower is not less than the distance from
i >th tower to
kth tower, and
kth tower is taller than
jth tower. Tower
j reachable from tower
i if there is a sequence of valid jumps that starts at the
ith tower and ends at
jth. Count for each tower the number of towers reachable from it, including itself.
Input
The first line of the input contains a single integer n (1 <= n <= 500000) - number of towers.< /p>
The second input line contains n numbers a1, a2< /code>, ..., an (1 <= a< sub>n <= 109) - tower heights.
Imprint
Print
n numbers, the
ith of which should be equal to the number of towers reachable from the
ith tower.
Note
In the first example, you can jump from 1st tower to 1 and 5 towers. Any other tower has a lower height than tower 1, so it cannot be jumped ( k can be chosen as 1). The set reachable from 1st tower also consists of towers 1 and 5. From the second tower you can jump to towers 1, 2, and 5, they are also a lot of reachable ones. From the third tower you can jump to towers 2, 3, 5. However, the 1 tower is also reachable, since two jumps can be made: 3→2→1. Thus, it turns out 4 reachable towers. From the 4th tower you can jump to the 4th and 5th towers, they are also the only ones reachable. From the 5th tower, only it is reachable.
In the second example, towers 1,2,3,4,5 are reachable from 1st and 2nd towers. Towers 3,4,5 are reachable from the 3rd tower. Towers 4,5 are reachable from 4th and 5th towers. Towers 4,5,6 are reachable from the 6th tower. Towers 4,5,6,7 are reachable from 7th tower.
Examples
| # |
Input |
Output |
| 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
|