#include<bits/stdc++.h>
using namespace std;

const int N=500100;

int n;

void calc(int*f,int*g){
    for(int i=1;i<=n;++i)
        g[i]=0;
    for(int i=1;i<n;++i){
        int mx=0;
        for(int j=i+1;j<=n;++j){
            if(max(f[i],f[j])>mx){
                ++g[i];
                ++g[j];
            }
            mx=max(mx,f[j]);
        }
    }
}


int a[N];
int ql,qr,qans;
int qid;

int mx[N*4],mn[N*4],mxid[N*4];


void bt(int o,int l,int r){
    if(l==r){
        mx[o]=mn[o]=a[l];
        mxid[o]=l;
        return;
    }
    int mid=(l+r)/2;
    bt(o*2,l,mid);
    bt(o*2+1,mid+1,r);
    mx[o]=max(mx[o*2],mx[o*2+1]);
    mxid[o]=(mx[o]==mx[o*2]?mxid[o*2]:mxid[o*2+1]);
    mn[o]=min(mn[o*2],mn[o*2+1]);
}

void query_min(int o,int l,int r){
    if(ql<=l&&r<=qr){
        qans=min(qans,mn[o]);
        return;
    }
    int mid=(l+r)/2;
    if(ql<=mid)
        query_min(o*2,l,mid);
    if(qr>mid)
        query_min(o*2+1,mid+1,r);
}
void query_max(int o,int l,int r){
    if(ql<=l&&r<=qr){
        qans=max(qans,mx[o]);
        return;
    }
    int mid=(l+r)/2;
    if(ql<=mid)
        query_max(o*2,l,mid);
    if(qr>mid)
        query_max(o*2+1,mid+1,r);
}
void query_maxid(int o,int l,int r){
    if(ql<=l&&r<=qr){
        if(mx[o]>qans){
            qans=mx[o];
            qid=mxid[o];
        }
        return;
    }
    int mid=(l+r)/2;
    if(ql<=mid)
        query_maxid(o*2,l,mid);
    if(qr>mid)
        query_maxid(o*2+1,mid+1,r);

}

int range_min(int l,int r){
    ql=l;qr=r;qans=INT_MAX;
    query_min(1,1,n);
    return qans;
}

int range_max(int l,int r){
    ql=l;qr=r;qans=0;
    query_max(1,1,n);
    return qans;
}

int range_argmax(int l,int r){
    ql=l;qr=r;qans=0;qid=0;
    query_maxid(1,1,n);
    return qid;
}

bool chk(int l,int r,int x){
    if(l>r)
        return 0;
    if(range_max(l,r)-x>r-l)
        return 1;
    if(range_min(l,r)-x<=(l==r?-1:0))
        return 1;
    return 0;
}

vector<int>work(int tl,int t,int tr,int l,int r,int x){
 //   cout<<tl<<' '<<t<<' '<<tr<<' '<<l<<' '<<r<<' '<<x<<endl;
    vector<int>ret;
    ret.push_back(t);
    int i=t,ni=tl;
    for(;ni>l;){
        int mi=i-(a[ni]-x);
        if(mi<l||mi>=ni)
            return{};
        ret.push_back(ni);
        i=ni;ni=mi;
    }
    if(ni!=i){
        if(a[ni]-x==i-ni)
            ret.push_back(ni);
    }
    i=t;ni=tr;
    for(;ni<r;){
        int mi=(a[ni]-x)+i;
        if(mi>r||mi<=ni)
            return{};
        ret.push_back(ni);
        i=ni;ni=mi;
    }
    if(ni!=i){
        if(a[ni]-x==ni-i)
            ret.push_back(ni);
    }
    sort(ret.begin(),ret.end());
    if(chk(l,ret[0]-1,x+1))
        return{};
    if(chk(ret.back()+1,r,x+1))
        return{};
    for(int i=0;i<(int)ret.size()-1;++i)
        if(chk(ret[i]+1,ret[i+1]-1,x+2))
            return{};
    return ret;
}

int ans[N];

void solve(int l,int r,int x){
    if(l>r)
        return;
    if(l==r){
    //    assert(a[l]==x);
        ans[l]=1;
        return;
    }
    int t=range_argmax(l,r);
    if(a[t]==a[l])
        t=l;
    if(a[t]==a[r])
        t=r;
    //cout<<t<<endl;
    //assert(a[t]<=x+(r-l));
    if(a[t]==x+r-l){
        ans[t]=r-l+1;
        solve(l,t-1,x+1);
        solve(t+1,r,x+1);
        return;
    }
    int s=a[t]-x;
    for(int i=0;i<=s;++i){
        int tl=t-i,tr=t+s-i;
        if(tl<l||tr>r)continue;
        if(tl==t&&tl>l)continue;
        if(tr==t&&tr<r)continue;
        auto res=work(tl,t,tr,l,r,x);
        if(res.empty())
            continue;
        //cout<<res.size()<<endl;
       // for(int j:res)
     //   
     //       cout<<j<<'-';
     //   cout<<endl;
        for(int j:res)
            ans[j]=r-l+1;
        solve(l,res[0]-1,x+1);
        for(int j=0;j+1<(int)res.size();++j)
            solve(res[j]+1,res[j+1]-1,x+2);
        solve(res.back()+1,r,x+1);
        return;
    }
}
mt19937 rng(time(0));

int f[N];
int p[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    bt(1,1,n);
    solve(1,n,0);
    for(int i=1;i<=n;++i)
        cout<<ans[i]<<" \n"[i==n];
    return 0;
    n=10;
    for(;;){
        int mx=rng()%n+1;
        for(int i=1;i<=n;++i)
            p[i]=rng()%mx+1;
        calc(p,a);
        for(int i=1;i<=n;++i)
            cerr<<p[i]<<" \n"[i==n];
        for(int i=1;i<=n;++i)
            cerr<<a[i]<<" \n"[i==n];
        memset(ans,0,sizeof ans);
        solve(1,n,0);
        calc(ans,f);
        if(memcmp(a,f,sizeof a)){
            cout<<n<<'\n';
            for(int i=1;i<=n;++i)
                cout<<a[i]<<" \n"[i==n];
            for(int i=1;i<=n;++i)
                cout<<ans[i]<<" \n"[i==n];
            for(int i=1;i<=n;++i)
                cout<<f[i]<<" \n"[i==n];
            return 0;
        }
    }
    /*
    cin>>n;
    int mx=rng()%n+1;
    for(int i=1;i<=n;++i)
    for(int i=1;i<=n;++i)
        cin>>a[i];
    solve(1,n,0);
    for(int i=1;i<=n;++i)
        cout<<ans[i]<<" \n"[i==n];
    calc(ans,f);
    for(int i=1;i<=n;++i)
        cerr<<f[i]<<" \n"[i==n];
        */
}