Problem Description

In Donut Town, there is a super popular donut shop that always has a long line every day. There are currently $ N $ people standing in a straight line at this donut shop. Each person in the line is worried that the donuts might run out before it's their turn. The shop owner decided to calculate the "anxiety level" for each person to see how worried they are.

Let's call the person standing in the $ i $ -th position from the front ( $1 \leq i \leq N$ ) person $ i $. The height of person $ i $ is $ H_i $. The "anxiety level" of person $ i $ is defined as the number of people visible when person $ i $ looks forward. The conditions for person $ j $ to be visible to person $ i $ are as follows:

• Person $ j $ is standing in front of person $ i $. That is, $ j < i $.
• There is no person taller than person $ j $ between person $ i $ and person $ j $. That is, there is no $ k $ such that $ j < k < i $ and $ H_j < H_k $.

For example, if the heights of the people in line from front to back are $ 2, 5, 3, 4, 1 $, the person at the very back (person $ 5 $) can see person $ 2 $ and person $ 4 $ when looking forward, so the "anxiety level" of person $ 5 $ is $ 2 $.

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 an integer $ N $ ( $1 \leq N \leq 10^5$ ), representing the number of people in line.
• The second line contains $ N $ integers separated by spaces, where the $ i $ -th integer $ H_i $ ( $1 \leq H_i \leq 10^6$ ) represents the height of person $ i $. It is guaranteed that $H_p \neq H_q$ when $p \neq q$.

Output Format

The output consists of $ N $ lines. The $ i $ -th line should contain a single integer representing the "anxiety level" of person $ i $. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

5
2 5 3 4 1

Sample Output #1

0
1
1
2
2

Sample Input #2

1
1000000

Sample Output #2

0

Sample Input #3

8
66 52 56 32 27 50 72 23

Sample Output #3

0
1
2
2
3
4
3
1

Notes/Hints

Partial Points

This problem has partial points:

• If you correctly solve all test cases where $N \leq 100$, you will be awarded $ 10 $ points.
• If you correctly solve all test cases where $N \leq 5000$, you will be awarded $ 40 $ points.

见题面 Input 部分

见题面 Output 部分