Chain#8556
Given a sequence of integers a_1, a_2, ..., 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_{k_1}. Then do the same with a_{k_1} and denote the found element by a_{k_2}, and so on until we run out of the given sequence. Thus formed subsequence a_{k_1}, a_{k_2}, ..., we call chain beginning at index .
Write a program that outputs for any index the length of the corresponding chain that starts at index .
The first line contains positive integer n~(0 < n \le 500000). The second line contains the elements of the given sequence a_1, a_2, ..., a_n~(0 < a_i < 10^6).
Print in one line the sequence of chain’s lengths, corresponding to the elements of the input data.
Example 1