16539번 - Chain 다국어

Given is a sequence of N integers a₁, a₂, ..., a_n. For any element a_k (k = 1, 2, ..., n) we find the first larger than a_k element, which is placed to the right of a_k (if such exists). Denote it by a_k1. Then do the same with a_k1 and denote the found element by a_k2, and so on until we run out of the given sequence. Thus formed subsequence a_k1, a_k2, ..., 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 of the standard input, the value of N is written. On the second line, the elements of the given sequence are written, separated by spaces.

On a line in the standard output, your program has to 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.

• 0 < N < 500 000
• 0 < a_i < 1 000 000, for each i = 1, ..., N.