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 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 serious():
    #for _ in range(1000): testAVL()
    n = int(input())
    a = [int(x) for x in input().split()]
    res = calc(n, a)
    ans = ''
    for x in res[:-1]:
        ans += str(x)+' '
    ans += str(res[-1])
    print(ans)

def main():
    serious()
    #testHeap()
if __name__ == '__main__':
    main()
    