Given a sequence of n integers
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
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 < n ≤ 500000) is written. On the second line, the elements of the given sequence are written
an (0 <
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.
11 3 2 4 2 11 2 7 5 8 10 6
2 2 1 1 0 3 2 2 1 0 0