#include<bits/stdc++.h>

#include<ext/rope>

using namespace std;

using namespace __gnu_cxx;

#define R register int

#define AC 110000

#define getchar() *o++

char READ[],*o=READ;

int n,tot,maxn;

int s[AC],d[AC],ans[AC];

rope <int> tmp;

/*这大概是一道很妙的观察性质题吧，，，

可以观察到，对于插入任意一个数而言，不管插在哪里，对它前面的DP值是不会产生影响的，

而由于插入的数是递增的，所以插入这个数时，这个数自己就是当前数列里最大的那一个，

所以对后面的DP值也不会产生影响，所以其实只需要得到最后的序列直接DP即可以了，因为插入是无效的。

换句话来说，就是因为直接对最后序列查询得到的是不合法结果，当且仅当这个数的DP值中利用到了

在这个数前面的，且在它后面插入的数。而对于这道题而言，在它后面插入的数都比它大，

所以插在前面肯定查询不到，而插在后面自然也查不到了，所以直接做就好了

那如何处理输出问题呢？

因为时间顺序就是数字大小，因此把每个位置的DP值放入对应的数字大小里，然后前缀取max就可以了

*/

inline int read()

{

    int x=;char c=getchar();

    while(c > '' || c < '') c=getchar();

    while(c >= '' && c <= '') x=x*+c-'',c=getchar();

    return x;

}

void pre()

{

    n=read();

    for(R i=;i<=n;i++)

    {

        int a=read();

        tmp.insert(a,i);

    }

    //printf("!!!");

    for(R i=;i<=n;i++)

    {

    //    printf("%d\n",i);

        s[i]=tmp.at(i-);

    //    if(s[i] == 1) printf("!!!%d\n",i);

    }

}

void half(int x)

{

    int l=,r=tot,mid;

    while(l < r)

    {

        mid=(l + r) >> ;

        if(d[mid] > x) r=mid;//因为这里直接转移是保护了信息的，因此寻找第一个大于x的数

        else l=mid+;

    }

    d[l]=x;

    ans[x]=l;

}

//这种二分所利用的单调性实质上是因为前面被放入的后面一定可以用?

void work()

{

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

    //printf("\n");

    for(R i=;i<=n;i++)

    {

        if(s[i] > d[tot]) d[++tot]=s[i],ans[s[i]]=tot;

        else if(s[i] < d[]) d[]=s[i],ans[s[i]]=;//error!!!放入第一个ans当然=1了

        else half(s[i]);

        //ans[s[i]]=tot;//ans[s[i]]代表放入了s[i]后的最大ans，error 不能在这里就改最大ans,因为会统计到大于s[i]的ans

        //error!!!但还是要前缀和取max，因为这个只是统计到了s[i]的ans，还要考虑比s[i]小的数（之前插入）的ans

        //因为比s[i]小的数位置可能在右边，这个时候还没有统计到

    }//error!!!注意是存入对应的值所在位置

    for(R i=;i<=n;i++)

    {

        maxn=max(maxn,ans[i]);

        printf("%d\n",maxn);

    }

}

int main()

{

//    freopen("in.in","r",stdin);

    fread(READ,,,stdin);

    pre();

    work();

//    fclose(stdin);

    return ;

}