Bài toán: Tìm vị trí gần nhất bên trái có giá trị nhỏ hơn

Đề bài

Cho một mảng gồm ~ n ~ số nguyên, nhiệm vụ của bạn là tìm với mỗi phần tử trong mảng, 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 ~.

Input

• Dòng đầu tiên chứa 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, \ldots, x_n ~: các giá trị trong mảng.

Output

• In ra ~ n ~ số nguyên. Số thứ ~ i ~ là vị trí gần nhất bên trái có giá trị nhỏ hơn ~ x_i ~. Nếu không có, in ~ 0 ~.

Ràng buộc

• ~ 1 \leq n \leq 2 \times 10^5 ~
• ~ 1 \leq x_i \leq 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:

• Phần tử thứ 2 (~ 5 ~): phần tử gần nhất bên trái nhỏ hơn là ~ 2 ~ tại vị trí ~ 1 ~.
• Phần tử thứ 3 (~ 1 ~): không có phần tử nào nhỏ hơn bên trái, nên in ~ 0 ~.
• Phần tử thứ 6 (~ 3 ~): phần tử gần nhất bên trái nhỏ hơn là ~ 1 ~ tại vị trí ~ 3 ~.