Giá trị nhỏ hơn gần nhất (Nearest Smaller Values)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $x_1,x_2,\ldots,x_n$. Với mỗi vị trí $i$, hãy tìm vị trí $j$ lớn nhất thỏa mãn $j<i$ và $x_j<x_i$. Nếu không tồn tại vị trí như vậy, đáp án của vị trí $i$ là $0$.

Input

Dòng đầu chứa số nguyên $n$. Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\ldots,x_n$.

Output

In $n$ số nguyên. Số thứ $i$ là vị trí gần nhất bên trái của $i$ có giá trị nhỏ hơn $x_i$, hoặc $0$ nếu không có.

Subtask

• Subtask 1 (30 điểm): $n\le2000$; các điều kiện khác giữ nguyên.
• Subtask 2 (70 điểm): $1\le n\le 2\cdot10^5$, $1\le x_i\le10^9$.

Ví dụ

Input

8
2 5 1 4 8 3 2 5

Output

0 1 0 3 4 3 3 7

Giải thích

Ta xét lần lượt từng vị trí:

• $i=1$: bên trái không có phần tử nào, nên kết quả là $0$.
• $i=2$: $x_2=5$. Vị trí gần nhất bên trái có giá trị nhỏ hơn là $1$ vì $x_1=2<5$, nên kết quả là $1$.
• $i=3$: $x_3=1$. Cả $2$ và $5$ đều không nhỏ hơn $1$, nên kết quả là $0$.
• $i=4$: $x_4=4$. Ngay bên trái là $x_3=1<4$, nên kết quả là $3$.
• $i=5$: $x_5=8$. Ngay bên trái là $x_4=4<8$, nên kết quả là $4$.
• $i=6$: $x_6=3$. Hai giá trị gần hơn là $8$ và $4$ đều không nhỏ hơn $3$; $x_3=1<3$, nên kết quả là $3$.
• $i=7$: $x_7=2$. Các giá trị $3,8,4$ không nhỏ hơn $2$; $x_3=1<2$, nên kết quả là $3$.
• $i=8$: $x_8=5$. Ngay bên trái là $x_7=2<5$, nên kết quả là $7$.

Vì vậy dãy chỉ số cần in là 0 1 0 3 4 3 3 7.