Hàng cột

Ban kiến thiết đang tiến hành xây dựng một công trình gồm $n$ cây cột đặt thẳng hàng dọc theo bờ sông của kinh thành. Các vị trí dựng cột được đánh số thứ tự từ $1$ đến $n$. Tại mỗi vị trí $i$, một cây cột có chiều cao nguyên $a_i$ sẽ được dựng lên.

Để đảm bảo kết cấu cũng như mỹ quan tổng thể, chiều cao của các cây cột phải đáp ứng hai yêu cầu:

• Do nền đất tại mỗi vị trí có đặc tính khác nhau, cột tại vị trí thứ $i$ có chiều cao tối đa cho phép là $m_i$, nghĩa là $1 ≤ a_i ≤ m_i$.
• Theo quy chuẩn quy hoạch cảnh quan, không được phép có bất kỳ cây cột nào đồng thời thấp hơn cả một cây cột phía trước nó và một cây cột phía sau nó. Cụ thể, không tồn tại bộ ba chỉ số $j, i, k$ sao cho $j < i < k$ và $a_j > a_i < a_k$. Lưu ý rằng hai vị trí $j$ và $k$ không bắt buộc phải nằm sát vị trí $i$.

Ban kiến thiết muốn tối đa hóa tổng chiều cao của tất cả $n$ cây cột được xây dựng, tức là giá trị $\sum_{i=1}^n a_i$ đạt lớn nhất có thể. Hãy giúp ban kiến thiết chọn chiều cao $a_i$ cho từng cây cột thỏa mãn mọi quy định trên và có tổng chiều cao lớn nhất.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 ≤ n ≤ 500\,000$), biểu thị số lượng cột cần dựng.

Dòng thứ hai chứa $n$ số nguyên $m_1, m_2, ..., m_n$ ($1 ≤ m_i ≤ 10^9$), trong đó $m_i$ là giới hạn chiều cao tối đa cho cây cột tại vị trí thứ $i$.

Kết quả

In ra $n$ số nguyên $a_1, a_2, ..., a_n$ trên một dòng, phân tách nhau bởi dấu cách, thể hiện chiều cao của từng cây cột trong phương án tối ưu thỏa mãn tất cả các điều kiện đã nêu.

Nếu có nhiều phương án cùng đạt tổng chiều cao lớn nhất, có thể in ra bất kỳ phương án hợp lệ nào trong số đó.

Chấm điểm

Subtask 1 (30 points). $n ≤ 1000$

Subtask 2 (70 points). $1 ≤ n ≤ 500$\,000

Ví dụ

Input

5
1 2 3 2 1

Output

1 2 3 2 1

Ghi chú

Trong ví dụ trên, chiều cao của mỗi cột đều có thể chọn bằng đúng giới hạn tối đa cho phép. Dãy chiều cao [1, 2, 3, 2, 1] tăng dần rồi giảm dần, thỏa mãn tất cả các quy định về quy hoạch và đạt tổng chiều cao tối đa là 9.