Nhà chọc trời (dễ)

Một dãy $n$ lô đất nằm dọc theo một xa lộ, đánh số từ $1$ đến $n$. Trên mỗi lô đất sẽ xây đúng một toà nhà chọc trời. Vì tính chất nền đất khác nhau nên lô thứ $i$ có giới hạn số tầng tối đa là $m_i$: toà nhà ở lô $i$ với $a_i$ tầng phải thoả $1\le a_i\le m_i$.

Theo quy hoạch kiến trúc, không được phép tồn tại các chỉ số $j<i<k$ sao cho $a_j>a_i$ và $a_k>a_i$. Nói cách khác, mỗi toà nhà không được đồng thời có một toà cao hơn ở phía trái và một toà cao hơn ở phía phải (các lô $j,k$ không cần kề lô $i$).

Hãy chọn $a_1,a_2,\dots ,a_n$ tuân thủ mọi ràng buộc trên sao cho tổng $a_1+a_2+\dots +a_n$ đạt lớn nhất có thể.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số lô đất.
• Dòng thứ hai chứa $n$ số nguyên $m_1,m_2,\dots ,m_n$.

Dữ liệu ra

In ra $n$ số nguyên $a_1,a_2,\dots ,a_n$ cách nhau bởi dấu cách — kế hoạch xây tối ưu.

Nếu có nhiều phương án cùng đạt tổng lớn nhất, in ra bất kỳ phương án nào.

Ràng buộc

• $1\le n\le 1000$
• $1\le m_i\le {10}^9$

Ví dụ