1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 40000 + 10; 8 int a[maxn]; 9 int dp[maxn];10 11 int main(void)12 {13     #ifdef LOCAL14         freopen("1950in.txt", "r", stdin);15     #endif16 17     int N;18     scanf("%d", &N);19     while(N--)20     {21         int n;22         scanf("%d", &n);23         int i;24         for(i = 1; i <= n; ++i)25             scanf("%d", &a[i]);26         dp[1] = a[1];27         int len = 1;28 29         for(i = 2; i <= n; ++i)30         {31             int left = 1;32             int right = len;33             while(left <= right)34             {35                 int mid = (left + right) >> 1;36                 if(dp[mid] < a[i])37                     left = mid + 1;38                 else39                     right = mid - 1;40             }41             dp[left] = a[i];42             if(left > len)43                 ++len;44         }45         printf("%d\n", len);46     }47     return 0;48 }