#include <stdio.h>
#define MAX_POARTS 40000
int numOfTests;
int numOfPorts;
int arrayOfPorts[MAX_POARTS + 1];
//minTail[len]表示在所有長度為len的遞增子序列中的終止元素(也就是子序列中的最大值)裡面的最小值
int minTail[MAX_POARTS + 1];
//需要更新對應的minTail[lenOfIS]
int lenOfIS;//length of increasing subsequence
int result;//length of longest of increasing subsequence
//用二分搜尋的方法傳回minTail中port的下标,如果port不在minTail中,傳回第一個比port大的元素的下标
int binSearch(int port){
int start = 1;
int end = result;
while (start <= end){
int mid = (start + end) / 2;
if (port < minTail[mid])
end = mid - 1;
else if(port > minTail[mid])
start = mid + 1;
else
return mid;
}
return start;
}
int main(){
scanf("%d", &numOfTests);
int test;
for (test = 1; test <= numOfTests; test++){
scanf("%d", &numOfPorts);
int indexOfPort;
for (indexOfPort = 1; indexOfPort <= numOfPorts; indexOfPort++)
scanf("%d", &arrayOfPorts[indexOfPort]);
result = 1;
minTail[result] = arrayOfPorts[1];
for (indexOfPort = 2; indexOfPort <= numOfPorts; indexOfPort++){
int port = arrayOfPorts[indexOfPort];
lenOfIS = 0;
if (port <= minTail[1])
lenOfIS = 1;
else if (port > minTail[result])
lenOfIS = ++result;
else if (port < minTail[result])
lenOfIS = binSearch(port);
minTail[lenOfIS] = port;
}
printf("%d\n", result);
}
return 0;
}