原题：http://www.lydsy.com/JudgeOnline/problem.php?id=3173
题解：促使我写这题的动力是，为什么百度遍地是Treap，黑人问号？？？
这题可以用线段树做。我们知道，插入一个数只会使答案变大1或不变。用线段树维护长度为i的最长上升子序列末尾的位置。每插入一个数，可以在线段树中找出插入位置，然后更新即可。
#include <bits/stdc++.h>
#define N 100006
using namespace std;
int n,m,x,y,tot,f[N],s[10*N],flag[10*N];
inline int read()
{
int x=0,c=getchar();while(c<'0'||x>'9')c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-48,c=getchar();return x;
}
void down(int x)
{
if(flag[x]){
flag[x<<1]+=flag[x];
flag[x<<1|1]+=flag[x];
s[x]+=flag[x];
flag[x]=0;
}
}
void change(int i,int l,int r,int x,int y)
{
down(i);down(i<<1);down(i<<1|1);
if(l==r){s[i]=y;return;}
int mid=(l+r)>>1;
if(x<=mid)change(i<<1,l,mid,x,y);
else change(i<<1|1,mid+1,r,x,y);
s[i]=max(s[i<<1],s[i<<1|1]);
}
void add(int i,int l,int r,int x,int y)
{
down(i);down(i<<1);down(i<<1|1);
if(x<=l&&r<=y){flag[i]++;down(i);return;}
int mid=(l+r)>>1;
if(x<=mid)add(i<<1,l,mid,x,y);
if(y>mid)add(i<<1|1,mid+1,r,x,y);
s[i]=max(s[i<<1],s[i<<1|1]);
}
int query(int i,int l,int r,int x)
{
down(i);down(i<<1);down(i<<1|1);
if(l==r)return s[i];
int mid=(l+r)>>1;
if(x<=mid)return query(i<<1,l,mid,x);
return query(i<<1|1,mid+1,r,x);
}
int ask(int x)
{
int l=0,r=tot,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(query(1,1,n,mid)<=x)ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
int main()
{
n=read();
x=read();tot=1;
change(1,1,n,1,1);
printf("1\n");
for(int i=2;i<=n;i++){
x=read();
int tmp=ask(x);
if(tmp<tot)add(1,1,n,tmp+1,tot);
change(1,1,n,tmp+1,x+1);
tot=max(tot,tmp+1);
printf("%d\n",tot);
}
}