#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define ll long long

#define N 100050

using namespace std;

int n,rt,cnt,num,a[N],b[N],ans[N],ls[N],siz[N],rd[N],rs[N];

void update(int u){siz[u]=siz[ls[u]]+siz[rs[u]]+1;}

void lturn(int &u){

    int t=rs[u];rs[u]=ls[t];ls[t]=u;

    update(u);update(t);u=t;

}

void rturn(int &u){

    int t=ls[u];ls[u]=rs[t];rs[t]=u;

    update(u);update(t);u=t;

}

void insert(int &u,int k){

    if(!u){

        u=++cnt;siz[u]=1;

        rd[u]=rand();

        return;

    }

    siz[u]++;

    if(siz[ls[u]]<k){

        insert(rs[u],k-siz[ls[u]]-1);

        if(rd[rs[u]]<rd[u])lturn(u);

    }

    else{

        insert(ls[u],k);

        if(rd[ls[u]]<rd[u])rturn(u);

    }

}

void dfs(int x){

    if(!x)return;

    dfs(ls[x]);

    a[++num]=x;

    dfs(rs[x]);

}

void solve(){

    int tot=0;

    memset(b,0x3f,sizeof(b));

    for(int i=1;i<=n;i++){

        int p=lower_bound(b+1,b+1+n,a[i])-b;

        if(p>tot){

            b[++tot]=a[i];

            ans[a[i]]=tot;

        }

        else{

            ans[a[i]]=p;

            b[p]=a[i];

        }

    }

}

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        int p;

        scanf("%d",&p);

        insert(rt,p);

    }

    dfs(rt);solve();

    //for(int i=1;i<=n;i++)printf("%d ",a[i]);

    for(int i=1;i<=n;i++){

        ans[i]=max(ans[i],ans[i-1]);

        printf("%d\n",ans[i]);

    }

    return 0;

}