摇摆序列

Description

一个序列{bn}，满足b0>b1b3<…，称为摇摆序列。

给定一个长度为n的整数序列{an}，现在要在这个序列里找一个摇摆子序列，求摇摆子序列的最大长度。

Input

第一行为正整数t(≤50)，表示数据组数；每组数据中，第一行为正整数n(≤30000)，第二行为n个以空格隔开的正整数ai(<1000000)，输入保证在一组数据中，ai互不相同。

Output

对于每组数据，输出摇摆子序列的最大长度。

Sample Input 1

4 
5 
1 2 3 4 5 
5 
5 4 3 2 1 
5 
5 1 4 2 3 
5 
2 4 1 3 5

Sample Output 1

1
2
5
3

求大佬题解，谢谢