Mike is the president of country What-The-Fatherland. There are *n* bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to *n* from left to right. *i*-th bear is exactly *a*<sub class="lower-index">*i*</sub> feet high. 

A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strength of a group is the minimum height of the bear in that group.

Mike is a curious to know for each *x* such that 1 ≤ *x* ≤ *n* the maximum strength among all groups of size *x*.
The first line of input contains integer *n* (1 ≤ *n* ≤ 2 × 10<sup class="upper-index">5</sup>), the number of bears.

The second line contains *n* integers separated by space, *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>), heights of bears.

import heapq
n=int(input())
p=list(map(int, input().split(' ')))
left=[0]*n
right=[n-1]*n
stack=[]
for i in range (0,n):
    while stack and stack[-1][1]>=p[i]:
        stack.pop()
    if stack:
        left[i]=stack[-1][0]+1
    else:
        left[i]=0

    stack.append([i,p[i]])

stack=[]
for i in range (0,n):
    while stack and stack[-1][1]>=p[n-1-i]:
        stack.pop()
    if stack:
        right[n-1-i]=stack[-1][0]-1
    else:
        right[n-1-i]=n-1

    stack.append([n-1-i,p[n-1-i]])

y=[[right[i]-left[i]+1,p[i]] for i in range (0,n)]
y.sort(key=lambda x:x[0],reverse=True)
u=[]
ans=[0]*n
j=0
for i in range (0,n):
    l=n-i
    while j<=n-1 and y[j][0]>=l:
        heapq.heappush(u,-y[j][1])
        j=j+1
    x=heapq.heappop(u)
    ans[n-1-i]=-x
    heapq.heappush(u,x)

for i in range (0,n):
    print(ans[i],end=' ')









