Tower

Source: Baekjoon Online Judge

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ towers of distinct heights arranged from left to right and numbered $1$ through $N$. Every tower emits a horizontal laser to the left. The laser from tower $i$ is received by the first tower to its left whose height is greater than $H_i$; shorter towers do not block it. If no such tower exists, the answer is $0$. Determine the receiving tower for every transmitter.

Input

The first line contains $N$. The second line contains the $N$ tower heights from left to right. All heights are distinct.

Output

Print $N$ integers. The $i$-th integer is the index of the tower that receives the laser from tower $i$, or $0$ if no tower receives it.

Subtasks

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

Examples

Input

5
6 9 5 7 4

Output

0 0 2 2 4

Explanation

The tower heights are $6,9,5,7,4$.

• Tower $1$ has no tower to its left, so its answer is $0$.
• Tower $2$ has height $9$. Its laser passes tower $1$ of height $6<9$, and there is no taller tower farther left, so its answer is $0$.
• Tower $3$ has height $5$ and immediately meets tower $2$ of height $9>5$, so its answer is $2$.
• Tower $4$ has height $7$. Its laser passes tower $3$ of height $5$ and then reaches tower $2$ of height $9>7$, so its answer is $2$.
• Tower $5$ has height $4$ and immediately reaches tower $4$ of height $7>4$, so its answer is $4$.

Therefore the output is 0 0 2 2 4.