Submit solution
Points:
1.00 (partial)
Time limit:
1.0s
Memory limit:
256M
Author:
Problem types
Allowed languages
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho 1 dãy số có ~n~ phần tử, độ dốc của phần tử thứ ~i~ là ~i_{cost}~ được tính như sau:
- ~L~ là phần tử xa nhất phía bên trái ~i~ sao cho giá trị từ ~i~ đến ~L~ giảm dần.
- ~R~ là phần tử xa nhất phía bên phải ~i~ sao cho giá trị từ ~i~ đến ~R~ giảm dần.
- ~i_{cost}~ là số phần tử từ ~L~ đến ~R~.
- Lưu ý: "giảm dần" (không chấp nhận bằng nhau), khác với "không tăng"
Nhiệm vụ của bạn là tính ~i_{cost}~ của cả ~n~ phần tử.
Input
- Dòng đầu tiên gồm 1 số nguyên ~n~ (~1 \le n \le 2 \cdot 10^5~) là số lượng phần tử.
- Dòng tiếp theo gồm ~n~ số nguyên ~A_1, A_2, …, A_N~ (~1 \le A_i \le 10^6~).
Output
In ra ~n~ số trên 1 hàng, cách nhau bởi 1 dấu cách là kết quả của bài toán.
Sample
Input #1
7
1 2 3 4 3 3 1
Output #1
1 2 3 5 1 2 1
Problem source: CLB Lập Trình PTIT
Comments