Buildings

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ buildings numbered $1$ through $N$, where building $i$ has height $H_i$. All heights are distinct. For every $i$, count the indices $j>i$ such that no building strictly between $i$ and $j$ is taller than building $j$.

Input

The first line contains $N$. The second line contains $N$ integers $H_1,H_2,\ldots,H_N$.

Output

Print $N$ integers; the $i$-th integer is the number of buildings $j$ satisfying the condition for building $i$.

Subtasks

• Subtask 1 (30 points): $N\le2000$; all other conditions are unchanged.
• Subtask 2 (70 points): $1\le N\le2\cdot10^5$, $1\le H_i\le N$, các $H_i$ đôi một khác nhau.

Examples

Input

5
2 1 4 3 5

Output

3 2 2 1 0

Explanation

The heights are $2,1,4,3,5$.

• For $i=1$, the valid indices are $j=2,3,5$. Index $j=4$ is invalid because building $3$ of height $4$ lies between them and is taller than building $4$ of height $3$. Hence $c_1=3$.
• For $i=2$, $j=3$ and $j=5$ are valid, while $j=4$ is blocked by the taller building $3$. Thus $c_2=2$.
• For $i=3$, both $j=4$ and $j=5$ satisfy the condition, so $c_3=2$.
• For $i=4$, only $j=5$ is available and valid, so $c_4=1$.
• For $i=5$, there is no building to the right, so $c_5=0$.

Therefore the program prints 3 2 2 1 0.