Queue

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

There are $n$ people in a queue from left to right, where person $i$ has value $a_i$. For every $i$, find the farthest position $j>i$ to the right such that $a_j<a_i$. If it exists, print the number of people strictly between $i$ and $j$, namely $j-i-1$; otherwise print $-1$.

Input

The first line contains $n$. The second line contains $n$ integers $a_1,a_2,\ldots,a_n$.

Output

Print $n$ integers in position order.

Subtasks

• Subtask 1 (30 points): $n\le2000$; all other conditions are unchanged.
• Subtask 2 (70 points): $2\le n\le10^5$, $1\le a_i\le10^9$.

Examples

Input

6
10 8 5 3 50 45

Output

2 1 0 -1 0 -1

Explanation

The values are $10,8,5,3,50,45$.

• Position $1$ has value $10$. The farthest smaller value to the right is $3$ at position $4$. Positions $2$ and $3$ lie between them, so the answer is $2$.
• Position $2$ has value $8$. The farthest smaller value is again at position $4$; only position $3$ lies between them, so the answer is $1$.
• Position $3$ has value $5$. Position $4$ has value $3<5$, and there is no farther smaller value, so the number of positions between them is $0$.
• Position $4$ has value $3$. No smaller value exists to its right, so the answer is $-1$.
• Position $5$ has value $50$. Position $6$ has value $45<50$ and is adjacent, so the answer is $0$.
• Position $6$ has nobody to its right, so the answer is $-1$.

Therefore the output is 2 1 0 -1 0 -1.