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_{i} feet high. 

 [Image] 

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.


-----Input-----

The first line of input contains integer n (1 ≤ n ≤ 2 × 10^5), the number of bears.

The second line contains n integers separated by space, a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), heights of bears.


-----Output-----

Print n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.


-----Examples-----
Input
10
1 2 3 4 5 4 3 2 1 6

Output
6 4 4 3 3 2 2 1 1 1

Difficulty: competition

Starter code:

Solutions:
def read_data():
    n = int(input())
    hs = list(map(int, input().split()))
    return n, hs


def solve(n, hs):
    left = get_left_index(n, hs)
    right = get_right_index(n, hs)
    vals = [[] for i in range(n)]
    for h, l, r in zip(hs, left, right):
        vals[r - l - 2].append(h)
    min_hs = []
    min_h = - float('inf')
    for val in vals[::-1]:
        for v in val:
            min_h = max(min_h, v)
        min_hs.append(min_h)
    print(* min_hs[::-1])


def get_left_index(n, hs):
    left = []
    stack = []
    for i, h in enumerate(hs):
        while stack and hs[stack[-1]] >= h:
            del stack[-1]
        if stack:
            left.append(stack[-1])
        else:
            left.append(-1)
        stack.append(i)
    return left


def get_right_index(n, hs):
    hs.reverse()
    tmp = get_left_index(n, hs)
    hs.reverse()
    tmp.reverse()
    right = [n - 1 - a for a in tmp]
    return right

n, hs = read_data()
solve(n, hs)

import math
import random

class AVLTree():
    def __init__(self, x):
        self.left = None
        self.rght = None
        self.val = x
        self.height = 1
        
def getHeight0(root):
    if root==None: return 0
    return max(getHeight0(root.left), getHeight0(root.rght))+1

def getHeight(root):
    if root==None: return 0
    return root.height
    #return max(getHeight(root.left), getHeight(root.rght))+1

def insert(root, x):
    if root==None: return AVLTree(x)
    if x==root.val: return root
    if x<root.val:
        root.left = insert(root.left, x)
    elif x>root.val:
        root.rght = insert(root.rght, x)
    hl = getHeight(root.left)
    hr = getHeight(root.rght)
    root.height = max(hl,hr)+1
    
    if hr-hl>1:
        assert hr-hl==2
        hrr=getHeight(root.rght.rght)
        hrl=getHeight(root.rght.left)
        if hrr==hrl+1:
            new_root = root.rght
            root.rght = new_root.left
            new_root.left = root
            root.height -= 2
            return new_root
        elif hrl==hrr+1:
            new_root = root.rght.left
            root.rght.left = new_root.rght
            new_root.rght = root.rght
            root.rght = new_root.left
            new_root.left = root
            root.height -= 2
            new_root.height += 1
            new_root.rght.height -= 1
            return new_root
        else:
            assert False
    elif hl-hr>1:
        assert hl-hr==2
        hlr=getHeight(root.left.rght)
        hll=getHeight(root.left.left)
        if hll==hlr+1:
            new_root = root.left
            root.left = new_root.rght
            new_root.rght = root
            root.height -= 2
            return new_root
        elif hlr==hll+1:
            new_root = root.left.rght
            root.left.rght = new_root.left
            new_root.left = root.left
            root.left = new_root.rght
            new_root.rght = root
            root.height -= 2
            new_root.height += 1
            new_root.left.height -= 1
            return new_root
        else:
            assert False
    return root

def findUpperBound(root, x):
    if root==None: return None
    if x>=root.val:
        return findUpperBound(root.rght, x)
    tmp_bound = findUpperBound(root.left, x)
    if tmp_bound==None: return root.val
    return tmp_bound
    
def findLowerBound(root, x):
    if root==None: return None
    if x<=root.val:
        return findLowerBound(root.left, x)
    tmp_bound = findLowerBound(root.rght, x)
    if tmp_bound==None: return root.val
    return tmp_bound
    
def inorder(root):
    if root==None: return []
    return inorder(root.left)+[root.val]+inorder(root.rght)

def checkHeight(root):
    if root==None: return True
    if not checkHeight(root.left): return False
    if not checkHeight(root.rght): return False
    return abs(getHeight0(root.left)-getHeight0(root.rght))<=1
    
def testAVL():
    l = [x for x in range(100)]
    for i in range(100):
        ni = random.randint(0,99)
        l[i],l[ni] = l[ni],l[i]

    tree = None
    for v in l:
        tree = insert(tree, v)
    assert inorder(tree)==[i for i in range(100)]
    assert checkHeight(tree)==True


class HeapObj():
    def __init__(self, v, n):
        self.val = v
        self.hpidx = n
        
def shiftup(n, r, hp):
    while r>=0:
        j = r*2+1
        if j<n:
            if j+1<n and hp[j+1].val>hp[j].val: j+=1
            if hp[j].val <= hp[r].val: return
            hp[r],hp[j] = hp[j],hp[r]
            hp[r].hpidx = r
            hp[j].hpidx = j
        if r==0: break
        r = int((r-1)/2)

def shiftdown(n, r, hp):
    while r<n:
        j = r*2+1
        if j>=n: return
        if j+1<n and hp[j+1].val>hp[j].val: j+=1
        if hp[j].val<=hp[r].val: return
        hp[r],hp[j] = hp[j],hp[r]
        hp[r].hpidx = r
        hp[j].hpidx = j
        r = j

def testHeap():
    hp = []
    for _ in range(100):
        obj = HeapObj(random.randint(0,9999), len(hp))
        hp.append(obj)
        shiftup(len(hp),len(hp)-1,hp)
    res = []
    while hp:
        res.append(hp[0].val)
        hp[0],hp[-1] = hp[-1],hp[0]
        hp[0].hpidx = 0
        hp.pop()
        shiftdown(len(hp), 0, hp)
    assert res==sorted(res, reverse=True)
    
def calc(n, a):
    ia = [x for x in enumerate(a)]
    ia.sort(key=lambda tp:tp[1])
    #print('ia={ia}'.format(ia=ia))
    tree = None
    tree = insert(tree, -1)
    tree = insert(tree, n)
    
    hpobj = HeapObj(n,0)
    hp = [hpobj]
    itv2hpobj = {(0,n-1):hpobj}
    ret = []
    nxt = n
    for idx,val in ia:
        #Get interval
        interval_end = findUpperBound(tree, idx)-1
        interval_bgn = findLowerBound(tree, idx)+1
        itv = (interval_bgn, interval_end)
        assert itv in itv2hpobj
        tree = insert(tree, idx)
        #Delete this interval from heap
        itv2hpobj[itv].val = 2*n
        hpidx = itv2hpobj[itv].hpidx
        shiftup(len(hp), hpidx, hp)
        hp[0],hp[-1] = hp[-1],hp[0]
        hp[0].hpidx = 0
        hp.pop()
        del itv2hpobj[itv]
        shiftdown(len(hp), 0, hp)
        
        #Add new interval(s) to heap
        if idx>interval_bgn:
            new_obj = HeapObj(idx-interval_bgn, len(hp))
            hp.append(new_obj)
            itv2hpobj[(interval_bgn,idx-1)] = new_obj
            shiftup(len(hp), len(hp)-1, hp)
        if idx<interval_end:
            new_obj = HeapObj(interval_end-idx, len(hp))
            hp.append(new_obj)
            itv2hpobj[(idx+1,interval_end)] = new_obj
            shiftup(len(hp), len(hp)-1, hp)
        NA = 0
        if len(hp)>0: NA = hp[0].val
        while nxt>NA:
            ret.append(val)
            nxt -= 1
    assert len(ret)==n
    ret.reverse()
    return ret

def calc_bf(n, a):
    ans = [None for _ in range(n)]
    for i in range(n):
        minij = None
        for j in range(i,n):
            l=j-i
            if minij == None or minij>a[j]:
                minij = a[j]
            if ans[l]==None or ans[l]<minij:
                ans[l] = minij
    return ans

def duipai():
    n = 10
    a = [random.randint(1,20) for _ in range(n)]
    res_smt = calc2(n, a)
    res_btf = calc_bf(n,a)
    if res_smt != res_btf:
        print('!')
        print(a)
        print(res_smt)
        print(res_btf)
        return False
    return True
def duipai_n(times):
    for i in range(times):
        print('Att {t}'.format(t=i))
        if not duipai(): break
        print()
        
def calc2(n, a):
    ans = [None for _ in range(n)]
    bst_intvs = [None for _ in range(n)]
    stk = [(-1,-2)]
    for idx,v in enumerate(a+[-1]):
        while v<=stk[-1][1]:
            bst_intvs[stk[-1][0]] = idx-stk[-2][0]-2
            stk.pop()
        stk.append((idx,v))
    for i in range(n):
        iv = bst_intvs[i]
        if ans[iv]==None or ans[iv]<a[i]:
            ans[iv] = a[i]
    #print('preans={0}'.format(ans))
    for i in range(n-2,-1,-1):
        if ans[i]==None or ans[i]<ans[i+1]:
            ans[i] = ans[i+1]
    return ans
    
def serious():
    n = int(input())
    a = [int(x) for x in input().split()]
    res = calc2(n, a)
    ans = ''
    for x in res[:-1]:
        ans += str(x)+' '
    ans += str(res[-1])
    print(ans)

def main():
    #duipai_n(1000000)
    serious()
    #testHeap()
def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3

N = input()
N = int(N)
A = input().split(' ')
A = list(map(int, A))

def get_L(A):
    L_candidates = [] # increasing list of indices with A smaller than anything considered so far
    L = A[:]

    for i in range(len(A)):
        while L_candidates and A[L_candidates[-1]] >= A[i]:
            L_candidates.pop()
        if L_candidates:
            L[i] = L_candidates[-1]
        else:
            L[i] = -1
        L_candidates.append(i)
    return L

L = get_L(A)
R = [N - x - 1 for x in get_L(A[::-1])][::-1]

strengths = [0] * (N + 3)
for i in range(N):
    p = R[i] - L[i] - 1
    strengths[p] = max(strengths[p], A[i])

strengths = strengths[1:N+1]

strengths = strengths[::-1]
for i in range(1, N):
    strengths[i] = max(strengths[i], strengths[i-1])
strengths = strengths[::-1]

print(' '.join(map(str, strengths)))

#!/usr/bin/env python3

N = input()
N = int(N)
A = input().split(' ')
A = list(map(int, A))

def get_L(A):
    L_candidates = [] # increasing list of indices with A smaller than anything considered so far
    L = A[:]

    for i in range(len(A)):
        while L_candidates and A[L_candidates[-1]] >= A[i]:
            L_candidates.pop()
        if L_candidates:
            L[i] = L_candidates[-1]
        else:
            L[i] = -1
        L_candidates.append(i)
    return L

L = get_L(A)
R = [N - x - 1 for x in get_L(A[::-1])][::-1]

strengths = [0] * (N + 3)
for i in range(N):
    p = R[i] - L[i] - 1
    strengths[p] = max(strengths[p], A[i])

strengths = strengths[1:N+1]

for i in range(N-1)[::-1]:
    strengths[i] = max(strengths[i], strengths[i+1])

print(' '.join(map(str, strengths)))

N = int(input())

array = list(map(int, input().split()))

res = [0 for i in range(N+1)]
stack = [ (0, -1) ]

for ( i, height ) in enumerate(array):
    while stack[-1][0] >= height:
        num = stack[-1][0]
        stack.pop()
        length = i - stack[-1][1] - 1
        res[length] = max(res[length], num)

    stack.append( (height, i) )

while len(stack) > 1 :
    num = stack[-1][0]
    stack.pop()
    length = N - stack[-1][1] - 1
    res[length] = max(res[length], num)

for i in range(N-1, 0, -1): #From N-1 to 1
    res[i] = max(res[i], res[i+1])

print(' '.join(map(str, res[1:])) ) 


n=int(input())
r=[0]*(n+1)
a=[0]*(n+1)
a[1:-1]=list(map(int,input().split()))
s=[(0,0)]
for i in range(1,n+2):
 while a[i]<s[-1][0]:
  r[i-s[-2][1]-1]=max(s[-1][0],r[i-s[-2][1]-1])
  del s[-1]
 s+=[(a[i],i)]
for i in range(n): r[-i-2]=max(r[-i-2],r[-i-1])
print(' '.join(map(str,r[1:])))


import sys

def solve():
    n, = rv()
    h, = rl(1)
    smallertoleftindex = [-1] * n
    smallertorightindex = [n] * n
    temp = list()
    for i in range(n):
        while len(temp) > 0 and h[temp[-1]] >= h[i]: temp.pop(-1)
        smallertoleftindex[i] = -1 if len(temp) == 0 else temp[-1]
        temp.append(i)
    temp = list()
    for i in range(n - 1, - 1, - 1):
        while len(temp) > 0 and h[temp[-1]] >= h[i]: temp.pop(-1)
        smallertorightindex[i] = n if len(temp) == 0 else temp[-1]
        temp.append(i)
    res = [0] * (n + 1)
    for i in range(n):
        nums = smallertorightindex[i] - smallertoleftindex[i] - 1
        res[nums] = max(res[nums], h[i])
    for i in range(n - 1, 0, -1): res[i] = max(res[i], res[i + 1])
    print(' '.join(map(str, res[1:])))

def prt(l): return print(''.join(l))
def rv(): return map(int, input().split())
def rl(n): return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
solve()

import sys

def solve():
    n, = rv()
    h, = rl(1)
    smallertoleftindex = [-1] * n
    smallertorightindex = [n] * n
    temp = list()
    for i in range(n):
        while len(temp) > 0 and h[temp[-1]] >= h[i]: temp.pop(-1)
        smallertoleftindex[i] = -1 if len(temp) == 0 else temp[-1]
        temp.append(i)
    temp = list()
    for i in range(n - 1, - 1, - 1):
        while len(temp) > 0 and h[temp[-1]] >= h[i]: temp.pop(-1)
        smallertorightindex[i] = n if len(temp) == 0 else temp[-1]
        temp.append(i)
    res = [0] * (n + 1)
    for i in range(n):
        nums = smallertorightindex[i] - smallertoleftindex[i] - 1
        res[nums] = max(res[nums], h[i])
    for i in range(n - 1, 0, -1): res[i] = max(res[i], res[i + 1])
    print(' '.join(map(str, res[1:])))

def prt(l): return print(''.join(l))
def rv(): return map(int, input().split())
def rl(n): return [list(map(int, input().split())) for _ in range(n)]
if sys.hexversion == 50594544 : sys.stdin = open("test.txt")
solve()

n = int(input())
a = [0] + list(map(int,input().split())) + [0]
r = [0] * (n + 1)
st = [(0, 0)]
for i in range(1, n + 2):
 	while a[i] < st[-1][0]:
  		r[i - st[-2][1] - 1] = max(st[-1][0], r[i - st[-2][1] - 1])
  		st.pop()
 	st.append((a[i], i))
for i in range(n): r[-i - 2] = max(r[-i - 2], r[-i - 1])
print(*r[1:]) 

__author__ = 'kitkat'
import sys

#sys.stdin = open("in.txt")
MAXN = int(2e5+10)
try:
    while True:
        S = [0] * MAXN
        ans = [0] * MAXN
        L = [0] * MAXN
        R = [0] * MAXN
        n = int(input())
        val = list(map(int, input().split(" ")))
        top = -1
        for i in range(n):
            while ~top and val[i] <= val[S[top]]:
                top -= 1
            L[i] = S[top] if ~top else -1
            top += 1
            S[top] = i
        top = -1
        for i in range(n-1, -1, -1):
            while ~top and val[i] <= val[S[top]]:
                top -= 1
            R[i] = S[top] if ~top else n
            top += 1
            S[top] = i
        for i in range(n):
            ans[R[i] - L[i] - 1] = max(ans[R[i] - L[i] - 1], val[i])
        for i in range(n-1, 0, -1):
            ans[i] = max(ans[i], ans[i+1])
        for i in range(1, n+1):
            sys.stdout.write('%d '%ans[i])
        print("")
except EOFError:
    pass


n=int(input())
r=[0]*(n+1)
a=[0]*(n+1)
a[1:-1]=list(map(int,input().split()))
s=[(0,0)]
for i in range(1,n+2):
 while a[i]<s[-1][0]:
  r[i-s[-2][1]-1]=max(s[-1][0],r[i-s[-2][1]-1])
  del s[-1]
 s+=[(a[i],i)]
for i in range(n): r[-i-2]=max(r[-i-2],r[-i-1])
print(' '.join(map(str,r[1:])))


# for _ in range(int(input())):
n = int(input())
arr = list(map(int,input().split()))
left,right = [-1]*n,[n]*n
ans = [0]*n
st = [0]
for i in range(1,n):
    while st and arr[st[-1]]>=arr[i]:
        st.pop()
    if st: left[i] = st[-1]
    st.append(i)
st = [n-1]
for i in range(n-2,-1,-1):
    while st and arr[st[-1]]>=arr[i]:
        st.pop()
    if st: right[i] = st[-1]
    st.append(i)
for i in range(n):
    ans[right[i]-left[i]-2] = max(ans[right[i]-left[i]-2],arr[i])
ans[0] = max(arr)
ans[-1] = min(arr)
for i in range(n-2,0,-1):
    ans[i] = max(ans[i],ans[i+1])
print(" ".join(map(str,ans)))

n=int(input())
r=[0]*(n+1)
a=[0]*(n+1)
a[1:-1]=list(map(int,input().split()))
s=[(0,0)]
for i in range(1,n+2):
 while a[i]<s[-1][0]:
  r[i-s[-2][1]-1]=max(s[-1][0],r[i-s[-2][1]-1])
  del s[-1]
 s+=[(a[i],i)]
for i in range(n): r[-i-2]=max(r[-i-2],r[-i-1])
print(' '.join(map(str,r[1:])))
 


n=int(input())
r=[0]*(n+1)
a=[0]*(n+1)
a[1:-1]=list(map(int,input().split()))
s=[(0,0)]
for i in range(1,n+2):
 while a[i]<s[-1][0]:
  r[i-s[-2][1]-1]=max(s[-1][0],r[i-s[-2][1]-1])
  del s[-1]
 s+=[(a[i],i)]
for i in range(n): r[-i-2]=max(r[-i-2],r[-i-1])
print(' '.join(map(str,r[1:])))
 


n=int(input())
r=[0]*(n+1)
a=[0]*(n+1)
a[1:-1]=list(map(int,input().split()))
s=[(0,0)]
for i in range(1,n+2):
 while a[i]<s[-1][0]:
  r[i-s[-2][1]-1]=max(s[-1][0],r[i-s[-2][1]-1])
  del s[-1]
 s+=[(a[i],i)]
for i in range(n): r[-i-2]=max(r[-i-2],r[-i-1])
print(' '.join(map(str,r[1:])))
 


n=int(input())
r=[0]*(n+1)
a=[0]*(n+1)
a[1:-1]=list(map(int,input().split()))
s=[(0,0)]
for i in range(1,n+2):
 while a[i]<s[-1][0]:
  r[i-s[-2][1]-1]=max(s[-1][0],r[i-s[-2][1]-1])
  del s[-1]
 s+=[(a[i],i)]
for i in range(n): r[-i-2]=max(r[-i-2],r[-i-1])
print(' '.join(map(str,r[1:])))
 


n=int(input())
r=[0]*(n+1)
a=[0]*(n+1)
a[1:-1]=list(map(int,input().split()))
s=[(0,0)]
for i in range(1,n+2):
 while a[i]<s[-1][0]:
  r[i-s[-2][1]-1]=max(s[-1][0],r[i-s[-2][1]-1])
  del s[-1]
 s+=[(a[i],i)]
for i in range(n): r[-i-2]=max(r[-i-2],r[-i-1])
print(' '.join(map(str,r[1:])))
 


n=int(input())
r=[0]*(n+1)
a=[0]*(n+1)
a[1:-1]=list(map(int,input().split()))
s=[(0,0)]
for i in range(1,n+2):
 while a[i]<s[-1][0]:
  r[i-s[-2][1]-1]=max(s[-1][0],r[i-s[-2][1]-1])
  del s[-1]
 s+=[(a[i],i)]
for i in range(n): r[-i-2]=max(r[-i-2],r[-i-1])
print(' '.join(map(str,r[1:])))
 


n=int(input())
r=[0]*(n+1)
a=[0]*(n+1)
a[1:-1]=list(map(int,input().split()))
s=[(0,0)]
for i in range(1,n+2):
 while a[i]<s[-1][0]:
  r[i-s[-2][1]-1]=max(s[-1][0],r[i-s[-2][1]-1])
  del s[-1]
 s+=[(a[i],i)]
for i in range(n): r[-i-2]=max(r[-i-2],r[-i-1])
print(' '.join(map(str,r[1:])))
 


n=int(input())
r=[0]*(n+1)
a=[0]*(n+1)
a[1:-1]=list(map(int,input().split()))
s=[(0,0)]
for i in range(1,n+2):
 while a[i]<s[-1][0]:
  r[i-s[-2][1]-1]=max(s[-1][0],r[i-s[-2][1]-1])
  del s[-1]
 s+=[(a[i],i)]
for i in range(n): r[-i-2]=max(r[-i-2],r[-i-1])
print(' '.join(map(str,r[1:])))
 




# Made By Mostafa_Khaled




n = int(input().strip())
a=list(map(int,input().strip().split()))

ans=[0]*(n+1)

#labirentin cevresine attigim 0lar gibi indexOut yememek icin
a=[0]+a+[0]
s=[]

for index,value in enumerate(a):
    #print('SS -> ',s)
    #print('ANS -> ',ans,'\n')
    #buyuk oldukca devam et 
    while s and value<s[-1][0]:
        ans[index-s[-2][1]-1]=max(s[-1][0],ans[index-s[-2][1]-1])
        s.pop()
    s.append((value,index))

#print('SS -> ', s)
#print('ANSS----',ans)

ans=ans[::-1]
for i in range(n):
    ans[i+1]=max(ans[i+1],ans[i])
ans=ans[::-1]
print(' '.join(map(str,ans[1:])))




"""

10
1 2 3 4 5 4 3 2 1 6

3
524125987 923264237 374288891

"""

n = list(map(int, input().split()))[0]
lst = list(map(int, input().split()))


sorted_index = sorted(range(n), key=lambda k: lst[k], reverse=True)

lookup = [(0, 0)] * n

res = []
res_pos = 1
for index in sorted_index:
    seq_len = lookup[index][0] + lookup[index][1] + 1
    if seq_len >= res_pos:
        step = seq_len - res_pos + 1
        res += [lst[index]] * step
        res_pos += step

    step_back = lookup[index][0] + 1
    if index - step_back >= 0:
        lookup[index - step_back] = (lookup[index - step_back][0],
                                     lookup[index - step_back][1] + 1 + lookup[index][1])

    step_forward = lookup[index][1] + 1
    if index + step_forward < n:
        lookup[index + step_forward] = (lookup[index + step_forward][0] + 1 + lookup[index][0],
                                        lookup[index + step_forward][1])


res = list(map(str, res))
print(" ".join(res))

N = int(input())
a = list(map(int, input().split()))
res = [0 for i in range(N+1)]
st = [ (0, -1) ]
for ( i, hh ) in enumerate(a):
    while st[-1][0] >= hh:
        num = st[-1][0]
        st.pop()
        ll = i - st[-1][1] - 1
        res[ll] = max(res[ll], num)

    st.append( (hh, i) )

while len(st) > 1 :
    num = st[-1][0]
    st.pop()
    ll = N - st[-1][1] - 1
    res[ll] = max(res[ll], num)

for i in range(N-1, 0, -1): 
    res[i] = max(res[i], res[i+1])

print(' '.join(map(str, res[1:])) )


n=int(input())
a=[int(o) for o in input().split()]
l=[-1]*n
r=[(n)]*n
stack=[]
for i in range(n):
  #  print(stack)
    while stack and a[stack[-1]]>=a[i]:
        stack.pop()
    if stack:
        l[i]=stack[-1]
    stack.append(i)
stack=[]
for i in range(n-1,-1,-1):
   # print(stack)
    while stack and a[stack[-1]]>=a[i]:
        stack.pop()
    if stack:
        r[i]=stack[-1]
    stack.append(i)
answers=[min(a)]*n
#print(l)
#print(r)

for i in range(n):
  #  print(r,l)
    lw=r[i]-l[i]-2
    #print(lw)
    
    answers[lw]=max(answers[lw],a[i])
    
ans=min(a)
answers[0]=max(a)
for i in range(n-1,-1,-1):
    ans=max(ans,answers[i])
    answers[i]=ans
print(*answers)




btqAIXPWRsBVCLo = int
btqAIXPWRsBVCLE = input
btqAIXPWRsBVCLp = list
btqAIXPWRsBVCLT = map
btqAIXPWRsBVCLN = range
btqAIXPWRsBVCLJ = max
btqAIXPWRsBVCLD = print
btqAIXPWRsBVCLy = str
btqAIXPWRsBVCLM = btqAIXPWRsBVCLo
btqAIXPWRsBVCLj = btqAIXPWRsBVCLE
btqAIXPWRsBVCLu = btqAIXPWRsBVCLp
btqAIXPWRsBVCLH = btqAIXPWRsBVCLT
btqAIXPWRsBVCLr = btqAIXPWRsBVCLN
btqAIXPWRsBVCLm = btqAIXPWRsBVCLJ
btqAIXPWRsBVCLa = btqAIXPWRsBVCLD
btqAIXPWRsBVCLf = btqAIXPWRsBVCLy
n = btqAIXPWRsBVCLM(btqAIXPWRsBVCLj())
r = [0]*(n+1)
a = [0]*(n+1)
a[1:-1] = btqAIXPWRsBVCLu(btqAIXPWRsBVCLH(btqAIXPWRsBVCLM,
                                          btqAIXPWRsBVCLj().split()))
s = [(0, 0)]
for i in btqAIXPWRsBVCLr(1, n+2):
    while a[i] < s[-1][0]:
        r[i-s[-2][1]-1] = btqAIXPWRsBVCLm(s[-1][0], r[i-s[-2][1]-1])
        del s[-1]
    s += [(a[i], i)]
for i in btqAIXPWRsBVCLr(n):
    r[-i-2] = btqAIXPWRsBVCLm(r[-i-2], r[-i-1])
btqAIXPWRsBVCLa(' '.join(btqAIXPWRsBVCLH(btqAIXPWRsBVCLf, r[1:])))