Có \(n\) người xếp thành một hàng dọc, người thứ \(i\) có chiều cao \(h_i\). Với mỗi người trong hàng, hãy tìm vị trí của người gần nhất về phía bên trái có chiều cao lớn hơn người đó.
Input
- Dòng đầu tiên chứa số nguyên \(n\): số lượng người trong hàng.
- Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, \ldots, h_n\): chiều cao của từng người.
- \(1 \leq n \leq 2 \cdot 10^5\)
- \(1 \leq h_i \leq 10^9\)
Output
In ra \(n\) số nguyên, số thứ \(i\) là vị trí của người gần nhất bên trái có chiều cao lớn hơn người thứ \(i\). Nếu không có người nào như vậy, in ra \(0\).
Example
Test 1
Input
8
2 5 1 4 8 3 2 5Output
0 0 2 2 0 5 6 5 Note
Giải thích:
- Người 1 (cao 2): không có ai bên trái \(\rightarrow\) 0
- Người 2 (cao 5): không có ai bên trái cao hơn 5 \(\rightarrow\) 0
- Người 3 (cao 1): người bên trái gần nhất cao hơn 1 là người 2 (cao 5) \(\rightarrow\) 2
- Người 4 (cao 4): người bên trái gần nhất cao hơn 4 là người 2 (cao 5) \(\rightarrow\) 2
- Người 5 (cao 8): không có ai bên trái cao hơn 8 \(\rightarrow\) 0
- Người 6 (cao 3): người bên trái gần nhất cao hơn 3 là người 5 (cao 😎 \(\rightarrow\) 5
- Người 7 (cao 2): người bên trái gần nhất cao hơn 2 là người 6 (cao 3) \(\rightarrow\) 6
- Người 8 (cao 5): người bên trái gần nhất cao hơn 5 là người 5 (cao 😎 \(\rightarrow\) 5
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.