给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

N行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。

 #include<bits/stdc++.h>

 using namespace std;

 #define MAXN 100010

 #define INF 1e9

 struct node

 {

     int left,right,val,size,count,rnd;

 }tree[MAXN];

 int ans[MAXN],v[MAXN],a[MAXN],SIZE,root,lv;

 int read()

 {

     int s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 void Update(int k){tree[k].size=tree[tree[k].left].size+tree[tree[k].right].size+;}

 void Lturn(int &k){int t=tree[k].right;tree[k].right=tree[t].left;tree[t].left=k;tree[t].size=tree[k].size;Update(k);k=t;}

 void Rturn(int &k){int t=tree[k].left;tree[k].left=tree[t].right;tree[t].right=k;tree[t].size=tree[k].size;Update(k);k=t;}

 void Insert(int &k,int x)

 {

     if(k==)

     {

         SIZE++;k=SIZE;

         tree[k].size=;tree[k].rnd=rand();

         return;

     }

     tree[k].size++;

     if(x<=tree[tree[k].left].size){Insert(tree[k].left,x);if(tree[tree[k].left].rnd<tree[k].rnd)Rturn(k);}

     else {Insert(tree[k].right,x-tree[tree[k].left].size-);if(tree[tree[k].right].rnd<tree[k].rnd)Lturn(k);}

 }

 void dfs(int k)

 {

     if(k==)return;

     dfs(tree[k].left);

     v[++lv]=k;

     dfs(tree[k].right);

 }

 int main()

 {

     int n,i,la,tmp,x;

     n=read();

     for(i=;i<=n;i++){x=read();Insert(root,x);}

     lv=;

     dfs(root);

     memset(ans,,sizeof(ans));

     la=;

     for(i=;i<=n;i++)a[i]=INF;

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

     {

         tmp=upper_bound(a+,a+la+,v[i])-a;

         a[tmp]=min(a[tmp],v[i]);

         ans[v[i]]=tmp;

         la=max(la,tmp);

     }

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

     {

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

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

     }

     return ;

 }