Nearest Smaller Values

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Given an array $x_1,x_2,\ldots,x_n$. For every position $i$, find the largest position $j$ such that $j<i$ and $x_j<x_i$. If no such position exists, the answer for position $i$ is $0$.

Input

The first line contains an integer $n$. The second line contains $n$ integers $x_1,x_2,\ldots,x_n$.

Output

Print $n$ integers. The $i$-th integer is the nearest position to the left of $i$ whose value is smaller than $x_i$, or $0$ if it does not exist.

Subtasks

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

Examples

Input

8
2 5 1 4 8 3 2 5

Output

0 1 0 3 4 3 3 7

Explanation

Process the positions from left to right:

• $i=1$: there is no element to the left, so the answer is $0$.
• $i=2$: $x_2=5$. The nearest smaller value on the left is $x_1=2$, so the answer is $1$.
• $i=3$: $x_3=1$. Neither $2$ nor $5$ is smaller than $1$, so the answer is $0$.
• $i=4$: $x_4=4$. The immediately preceding value $x_3=1$ is smaller, so the answer is $3$.
• $i=5$: $x_5=8$. Since $x_4=4<8$, the answer is $4$.
• $i=6$: $x_6=3$. The closer values $8$ and $4$ are not smaller than $3$; $x_3=1<3$, so the answer is $3$.
• $i=7$: $x_7=2$. The values $3,8,4$ are not smaller than $2$; $x_3=1<2$, so the answer is $3$.
• $i=8$: $x_8=5$. The immediately preceding value $x_7=2$ is smaller, so the answer is $7$.

Hence the required index sequence is 0 1 0 3 4 3 3 7.