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.
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
    int n;cin>>n;
    vector<int>a(n),table1(n,-1),table2(n,n);
    for (int i=0;i<n;i++){
        cin>>a[i];
    }
    stack<int>st1,st2;
    for(int i=0;i<n;i++){
        while(!st1.empty() && a[st1.top()]>=a[i]){
            st1.pop();
        }
        if(!st1.empty()){
            table1[i]=st1.top();
        }
        else{
            table1[i]=-1;
        }
        st1.push(i);
        //cout<<table1[i]<<" ";
    }
    //cout<<endl;
    for(int i=n-1;i>=0;i--){
        while(!st2.empty() && a[st2.top()]>=a[i]){
            st2.pop();
        }
        if(!st2.empty()){
            table2[i]=st2.top();
        }
        else{
            table2[i]=n;
        }
        st2.push(i);
        //cout<<table2[i]<<" ";
    }
    //cout<<endl;
    vector<int>ans(n,0);
    for(int i=0;i<n;i++){
        int val=table2[i]-table1[i];
        if(val>=n){
            ans[n-1]=max(ans[n-1],a[i]);
        }
        else if(val>1){
            ans[val-2]=max(ans[val-1],a[i]);
        }
        else if(val==1){
            ans[0]=max(ans[0],a[i]);
        }

    }
    int tmp=ans[n-1];
    for(int i=n-1;i>=0;i--){
        tmp=max(tmp,ans[i]);
        ans[i]=tmp;
    }
    for(int i=0;i<n;i++)cout<<ans[i]<<" ";
    cout<<endl;
}