Problem Description

Takahashi is a mountaineer and is currently climbing a mountain range.

This mountain range has $ N $ mountain huts aligned in a straight line from west to east, and each hut is numbered from $ 1 $ to $ N $ in order from west to east.

The $ i $th mountain hut is built at an elevation of $ h_i $.

Takahashi is curious about how many mountain huts he can see from each hut.

The condition for the $ i $th hut to see the $ j $th hut is that all the huts between them and the $ j $th hut have elevations no more than $ h_i $.

Calculate the number of mountain huts that can be seen from each hut.

Note that the $ i $th hut itself is not included in the number of huts visible from the $ i $th hut.

Input Format

The input is given from the standard input in the following format:

$ N $ $ h_1 $ $ h_2 $ : $ h_N $

• The first line contains the number of mountain huts $N\ (1\ ≦\ N\ ≦\ 10^5)$.
• The next $ N $ lines contain the elevation of the $ i $th mountain hut as an integer $h_i\ (1\ ≦\ h_i\ ≦\ 10^5)$.

Output Format

The output consists of $ N $ lines. The $ i $th line should contain the number of mountain huts visible from the $ i $th hut.

Sample Input and Output

Sample Input #1

3
1
2
3

Sample Output #1

0
1
2

Sample Input #2

5
1
2
3
2
1

Sample Output #2

0
1
4
1
0

Sample Input #3

5
3
2
1
2
3

Sample Output #3

4
2
0
2
4

Sample Input #4

8
4
3
2
3
4
3
2
1

Sample Output #4

7
2
0
2
7
2
1
0

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $1\ ≦\ N\ ≦\ 3,000$, you will be awarded $ 30 $ points.
• If you solve the dataset where $1\ ≦\ N\ ≦\ 10^5$, you will be awarded an additional $ 70 $ points, totaling $ 100 $ points.

Sample Explanation 1

No hut can see any hut to its west.

Sample Explanation 2

The $ 1 $st and $ 5 $th huts cannot see any huts. The $ 2 $nd hut can see the $ 1 $st hut. The $ 4 $th hut can see the $ 5 $th hut. The $ 3 $rd hut can see all other huts.

Sample Explanation 3

Note that huts of the same elevation can barely be seen.

见题面 Input 部分

见题面 Output 部分