Chain

Given a sequence of $n$ 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 $k$.

Write a program that outputs for any index $k$ the length of the corresponding chain that starts at index $k$.

Input

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)$.

Output

Print in one line the sequence of chain’s lengths, corresponding to the elements of the input data.

Examples