Một công xưởng đã sản xuất ra một dãy \(n\) con chip được gắn liền kề với nhau, con chip thứ \(i\) đang hoạt động ở công suất \(a_{i}\). Vì được gắn liền kề nhau nên công suất của những con chip có sự tác động lẫn nhau và làm ảnh hưởng đến công suất hoạt động của cả đoạn. Ta định nghĩa tổng công suất của các con chip trong một đoạn chip \([l, r]\) \((1 \leq l \leq r \leq n)\) được xác định bởi giá trị nhỏ nhất của đoạn chip đó. Để chiết xuất một đoạn chip hoạt động hiệu quả, nhà sản xuất muốn biết rằng với mỗi số nguyên \(x\) từ \(1\) đến \(n\), đoạn chip có độ dài \(x\) có tổng công suất lớn nhất là bao nhiêu?

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 2 \times 10^{5})\) là số lượng chip của công xưởng.
• Dòng tiếp theo gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\) là công suất hoạt động của các con chip.

Output

• Gồm \(n\) số nguyên dương trên 1 dòng, số nguyên thứ \(x\) là tổng công suất lớn nhất của đoạn chip độ dài \(x\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 500\).
• Subtask \(2\) (\(10\%\) số điểm): \(n \leq 1000\).
• Subtask \(3\) (\(10\%\) số điểm): \(a_{i} \leq 100\).
• Subtask \(4\) (\(25\%\) số điểm): \(n \leq 5000\).
• Subtask \(5\) (\(35\%\) số điểm): không có ràng buộc gì thêm.

Example

4
2 1 4 5

5 4 1 1