a[0]=-999999999; a[n+1]=99999999;
k=1; d[1]=1;
for (int i=2; i<=n+1; i++) {
if (a[i]<a[d[1]]) {d[1]=i;} else if (a[i]>a[d[k]]) {k++;d[k]=i;} else {
d=1; c=k;
int vt=0;
while(d<=c){
int g=(d+c)/2;
if (a[i]>a[d[g]]) {vt=g;d=g+1;} else c=g-1;
}
}
d[vt]=i;
}
return k;