Mike và bầy gấu

Có $n$ chú gấu đứng thành một hàng, đánh số từ $1$ đến $n$ từ trái sang phải. Chú gấu thứ $i$ có chiều cao $a_i$.

Một nhóm gấu là một đoạn liên tiếp không rỗng các chú gấu trên hàng. Kích thước của nhóm là số gấu trong nhóm đó, còn độ mạnh của nhóm là chiều cao nhỏ nhất trong các chú gấu thuộc nhóm.

Với mỗi giá trị $x$ ($1\le x\le n$), hãy tìm độ mạnh lớn nhất trong tất cả các nhóm có kích thước đúng bằng $x$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số lượng gấu.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — chiều cao của các chú gấu.

Dữ liệu ra

In ra $n$ số nguyên trên một dòng. Số thứ $x$ là độ mạnh lớn nhất trong tất cả các nhóm có kích thước $x$.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le a_i\le {10}^9$

Ví dụ