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