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 a program that outputs for any index k the length of the corresponding chain that starts at index k.
The first line contains positive integer n (0<n≤500000). The second line contains the elements of the given sequence a1,a2,...,an (0<ai<106).
Print in one line the sequence of chain’s lengths, corresponding to the elements of the input data.