The NBA Draft has a lot of phenomenon players, and AD is one of them. Each player in position i has his body height hi.
As everyone knows, the NBA teams prefer tall players, and they consider it as good center material that would be a potential game-changer.
AD is interested in finding players shorter (i.e., with smaller heights) than him. AD calls those players with smaller heights than him the “shorties”.
Given n players standing in a line from left to right, we say that the first player is at position 1, the second player is at position 2, the n-th player is at position n, etc. Now, we need to help AD find the closest shorty to his left. Please note that we need to help AD on n tasks at once, i.e., finding each shorty when AD is at position 1, at position 2, …, and at position n.
The following is an example. Assume a set of 8 players are standing in a line, from left to right, denoted as (left) p1, p2, p3, …, p8 (right). Their respective heights are listed as follows.
|
Position |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
Player |
p1 |
p2 |
p3 |
p4 |
p5 |
p6 |
p7 |
P8 |
|
Height |
2 |
5 |
1 |
4 |
8 |
3 |
2 |
5 |
Now, we consider the following cases to help AD.
AD is at position 1: No one is on his left. Output 0.
AD is at position 2: The closest shorty to his left is at position 1. Output 1.
AD is at position 3: No shorty on his left. Output 0.
AD is at position 4: The closest shorty to his left is at position 3. Output 3.
AD is at position 5: The closest shorty to his left is at position 4. Output 4.
AD is at position 6: The closest shorty to his left is at position 3. Output 3.
AD is at position 7: The closest shorty to his left is at position 3. Output 3.
AD is at position 8: The closest shorty to his left is at position 7. Output 7.
The first line contains an integer n, which is the number of players.
The second line contains n numbers h1, h2, …, hn, indicating the heights of the players or AD.
Input ranges:
1 <= n <= 200,000
1 <= hi <= 1,000,000,000 , for all 1 <= i <= n
Print n numbers: If AD stands at position i, output the closest shoty’s position on AD’s left. If no such position, output 0.
Each output number has space behind it, and please print '\n' at the end of the output.