Cho một dãy $a$ gồm $n$ phần tử. Ta định nghĩa $g(l,r)=min(a[i])\mathrm{\forall }(l\le i\le r)$.

Tiếp đó, ta có $f(k)=max(g(l,r))\mathrm{\forall }(r-l+1=k)$, hay $f(k)$ là giá trị lớn nhất của các $g(l,r)$ với mọi đoạn $(l,r)$ có độ dài $k$.

Hãy lập trình tính các $f(k)$ từ $1->n$.

Input

• Dòng đầu tiên gồm số nguyên dương $n$. $(1\le n\le {10}^5).$
• Dòng sau gồm n số nguyên dương miêu tả dãy $a$. $(1\le a[i]\le {10}^6$ $\mathrm{\forall }(1\le i\le n))$.

Output

• In ra một dòng gồm $n$ số miêu tả kết quả của $f(k)$ từ $1->n$.

Sample Test

Input:

10
1 2 3 4 5 4 3 2 1 6

Output:

6 4 4 3 3 2 2 1 1 1