#include <cstdio>

 #include<algorithm>

 #define F(i,a,b) for(int i=a;i<=b;i++)

 using namespace std;

 const int N = 1e5+;

 int a[N],d[N];

 int LIS(int* a, int n, int* d){

     int len=;d[]=a[];

     F(i,,n)if(d[len]<a[i])d[++len]=a[i];

     else d[lower_bound(d+,d++len,a[i])-d]=a[i];

     return len;

 }

 int main(){

     int t,n;

     scanf("%d",&t);

     while(t--){

     scanf("%d",&n);

         for(int i =; i <=n; i++)scanf("%d",&a[i]);

         printf("%d\n",LIS(a,n,d));

     }

     return ;

 }

 这个是求LIS的线段树的代码

 #include<cstdio>

 #include<algorithm>

 #define root 1,n,1

 #define ls l,m,rt<<1

 #define rs m+1,r,rt<<1|1

 #define F(i,a,b) for(int i=a;i<=b;i++)

 using namespace std;

 const int N=1e5+;

 int n,sum[N<<],a[N],ans,dp[N];

 void update(int x,int k,int l,int r,int rt){

     if(l==r){sum[rt]=k;return;}

     int m=(l+r)>>;

     if(x<=m)update(x,k,ls);

     else update(x,k,rs);

     sum[rt]=max(sum[rt<<],sum[rt<<|]);

 }

 int query(int L,int R,int l,int r,int rt){

     if(L<=l&&r<=R)return sum[rt];

     int m=(l+r)>>,ret=;

     if(L<=m)ret=max(ret,query(L,R,ls));

     if(m<R)ret=max(ret,query(L,R,rs));

     return ret;

 }

 int main(){

     while(~scanf("%d",&n)){

         F(i,,n)scanf("%d",a+i),dp[i]=;

         F(i,,(N<<)-)sum[i]=;ans=;

         F(i,,n){

             if(a[i]->){

                 dp[i]=max(dp[i],query(,a[i]-,root))+;

                 update(a[i],dp[i],root);

             }else dp[i]=,update(a[i],dp[i],root);

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

         }

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

     }

     return ;

 }