Giá trị nhỏ hơn gần nhất bên trái

Bối cảnh và bài toán

Với mỗi điểm đo trong dãy, hệ thống cần tìm điểm gần nhất về bên trái có giá trị nhỏ hơn hiện tại. Nếu không có, trả 0.

Yêu cầu

Với mỗi vị trí i, in chỉ số 1-based gần nhất j<i sao cho a[j] < a[i], hoặc 0.

Input

• Dòng 1: n.
• Dòng 2: n số nguyên a[i].

Output

In n chỉ số.

Ràng buộc

• 1 <= n <= 2 * 10^5
• 1 <= a[i] <= 10^9

Chấm điểm

Ví dụ 1

Input

8
2 5 1 4 8 3 2 5

Output

0 1 0 3 4 3 3 7

Giải thích. Ví dụ vị trí 6 có giá trị 3; phần tử nhỏ hơn gần nhất bên trái là vị trí 3 có giá trị 1.

Ví dụ 2

Input

5
5 4 3 2 1

Output

0 0 0 0 0

Giải thích. Không vị trí nào có phần tử nhỏ hơn ở bên trái.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set – Nearest Smaller Values.

Tham khảo: https://cses.fi/problemset/task/1645