Runners in a long-distance race have passed the turning point. Each runner has a distinct integer ability; a larger value means a stronger runner. A runner can overtake any runner ahead whose ability is smaller, but cannot overtake a stronger runner.

Given the abilities in current race order, from front to back, find the best rank each runner can achieve.

For example, abilities $2,8,10,7,1,9,4,15$ give best ranks $1,1,1,3,5,2,5,1$. The fourth runner, with ability $7$, can pass the runner with ability $2$ but cannot pass those with abilities $8$ and $10$, so their best rank is $3$.

Input

The first line contains $N$ ($3 \le N \le 500000$). Each of the next $N$ lines contains one runner's ability, in current race order. Abilities are distinct integers between $1$ and $10^9$ inclusive.

Output

Print $N$ lines in input order, giving each runner's best rank. Rank 1 is first place.

Example

Input:

8
2
8
10
7
1
9
4
15

Output:

1
1
1
3
5
2
5
1