Đi rừng là một hoạt động được tổ chức thường xuyên trong câu lạc bộ để giúp các thành viên thư giãn sau những giờ phút miệt mài với bàn phím và dòng code. Nhưng hôm nay, không chỉ là một buổi đi rừng thông thường, mà là một cuộc thi kỹ năng sinh tồn được tổ chức ngay giữa khu rừng!

Có ~n~ thành viên tham gia cuộc thi. Thành viên thứ ~i~ được đánh giá kỹ năng thông qua chỉ số ~a_i~. Ban tổ chức quyết định chia các thành viên thành các nhóm liên tiếp, mỗi nhóm phải cạnh tranh dựa trên kỹ năng yếu nhất của nhóm mình. Cụ thể, kỹ năng của một nhóm được tính bằng giá trị nhỏ nhất trong chỉ số kỹ năng của các thành viên trong nhóm.

Để tăng độ kịch tính, mỗi đội trưởng phải báo cáo cho ban tổ chức rằng, với mỗi kích thước nhóm ~x~ (số thành viên trong nhóm là ~x~), nhóm mạnh nhất có thể đạt được kỹ năng cao nhất là bao nhiêu.

AliVu, người đứng đầu ban tổ chức, rất tò mò về kết quả này và muốn biết kỹ năng tối đa của nhóm mạnh nhất cho mỗi kích thước nhóm ~x~ ~(1 \le x \le n)~.

Input

• Dòng đầu tiên gồm một số nguyên ~n~ ~(1 \le n \le 2\times10^5)~ - số lượng thành viên tham gia.
• Dòng thứ hai là ~n~ số nguyên ~a_1, a_2,..., a_n~ ~(1 \le a_i \le 10^9~ - chỉ số kỹ năng của từng thành viên.

Output

• In ra ~n~ số nguyên trên một dòng. Với mỗi ~x~ ~(1 \le x \le n)~, in ra kỹ năng tối đa của nhóm mạnh nhất có kích thước là ~x~.

Sample Input 1

10  
1 2 3 4 5 4 3 2 1 6

Sample Output 1

6 4 4 3 3 2 2 1 1 1