Problem K
Couple Competition

Hori-san and Miyamura-kun have bought a new game to play with to show their precious and eternal love for one another. Being competitive and loving at the same time, they both want to win the game.

This game can be modelled in a form of $N$ rectangular blocks with a heights $1 \leq {h}_ i \leq 10^{9}$ for $i = 1,2,\ldots ,N$.

A jump is described as moving from the player’s current block to the nearest block in either the left and right direction that has a height strictly higher than it.

The aim of the game is to reach the highest block in the shortest number of jumps.

Miyamura wants to win at least one game over Hori, so he needs you to help him to compute the smallest number of jumps to reach the highest block starting from every possible starting block.

Input

The first line contains an integer, $1 \le N \le 1\, 000\, 000$, the number of blocks.

The next $N$ lines contain the height of the blocks, $1 \leq {h}_ i \leq 10^{9}$, each on one line.

Output

Print out on one line, for every rectangular block, the minimum number of jumps to get to the highest block starting from it, followed by a space.

Subtasks

1. ($12$ Points): $N = 7$, at most 2 distinct heights.

2. ($12$ Points): $N = 10$, Moreover the height of the $N$ blocks are strictly increasing or strictly decreasing.

3. ($30$ Points): $N \le 100$.

4. ($24$ Points): $N \le 5\, 000$.

5. ($22$ Points): No additional constraint.

Warning

The input files are large. Please use fast I/O methods.

Explanation of Sample Input 1

The following are the explanations for Sample Input 1:

• Since block $1$ is the highest block, the number of jumps is $0$.

• Since block $2$ has only height $4$, Miyamura can only jump to block $1$ to the left of height $10$, or block $4$ to the right of height $8$.

• Since block $3$ has only height $2$, Miyamura can only jump to block $2$ to the left of height $4$, or block $4$ to the right of height $8$.

• Since block $4$ has only height $8$, Miyamura can only jump to block $1$ to the left of height $10$, or block $5$ to the right of height $10$.

• Since block $5$ is the highest block, the number of jumps is $0$.

5
10
4
2
8
10

0 1 2 1 0

6
1
2
3
4
5
6

5 4 3 2 1 0