Given a sequence of n integers a1, a2, ..., an. For any element ak (k = 1, 2, ..., n) we find the first larger than ak element, which is placed to the right of ak (if such exists). Denote it by ak1. Then do the same with ak1 and denote the found element by ak2, and so on until we run out of the given sequence. Thus formed subsequence ak1, ak2, ..., we call chain beginning at index k.

Write program chain that outputs for any index k the length of the corresponding chain that begins at index k.


On the first line the positive integer n (0 < n500000) is written. On the second line, the elements of the given sequence are written a1, a2, ..., an (0 < ai < 106), separated by spaces.


On a line write the sequence of chain’s lengths, corresponding to the element of the input data. Each two consecutive numbers in the output must be separated by a single space.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 2 4 2 11 2 7 5 8 10 6
Output example #1
2 2 1 1 0 3 2 2 1 0 0
Source 2017 IX International autumn tournament in informatics, Shumen, Junior, Day 2, Problem F