Cho dãy \(a\) gồm \(n\) số nguyên. Giá trị của một đoạn con gồm các phần tử liên tiếp là phần tử có giá trị nhỏ nhất thuộc đoạn con đó. Với mỗi \(x\) từ \(1\) đến \(n\), hãy tìm giá trị lớn nhất của đoạn con độ dài \(x\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 10^6)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\).

Output

• Gồm \(n\) số nguyên, số nguyên thứ \(x\) là giá trị lớn nhất của đoạn con độ dài \(x\).

Example

10
1 2 3 4 5 4 3 2 1 6

6 4 4 3 3 2 2 1 1 1