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

Trong một dự án mới tại bưu điện, FullHouse Dev được giao nhiệm vụ tối ưu hóa hệ thống sắp xếp bưu kiện. Họ nhận ra rằng việc tìm giá trị nhỏ hơn gần nhất trong một dãy số có thể giúp cải thiện quy trình phân loại. Với tinh thần nhiệt huyết, FullHouse Dev bắt đầu giải quyết bài toán này.

Bài toán

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là tìm cho mỗi vị trí trong mảng vị trí gần nhất bên trái có giá trị nhỏ hơn.

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(n\): kích thước của mảng.
• Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2, \dots, x_n\): các giá trị trong mảng.

OUTPUT FORMAT:

• In ra \(n\) số nguyên: với mỗi vị trí trong mảng, in ra vị trí gần nhất bên trái có giá trị nhỏ hơn. Nếu không có vị trí nào như vậy, in ra 0.

Ràng buộc:

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le x_i \le 10^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

• Với số 2 đầu tiên, không có số nào nhỏ hơn bên trái, nên kết quả là 0.
• Với số 5, số nhỏ hơn gần nhất bên trái là 2 ở vị trí 1.
• Với số 1, không có số nào nhỏ hơn bên trái, nên kết quả là 0.
• Với số 4, số nhỏ hơn gần nhất bên trái là 1 ở vị trí 3.
• Với số 8, số nhỏ hơn gần nhất bên trái là 4 ở vị trí 4.
• Với số 3, số nhỏ hơn gần nhất bên trái là 1 ở vị trí 3.
• Với số 2 thứ hai, số nhỏ hơn gần nhất bên trái là 1 ở vị trí 3.
• Với số 5 cuối cùng, số nhỏ hơn gần nhất bên trái là 2 ở vị trí 7.

Bằng cách giải quyết bài toán này, FullHouse Dev hy vọng sẽ cải thiện đáng kể hiệu suất của hệ thống phân loại bưu kiện tại bưu điện.