2011年12月17日 星期六

11240 - Antimonotonicity

給定一個稱為Fred的數列,共有 n 項,且每一項的數值分別介於 1~n 之間,任一對相鄰的項其值必不相同,本題要求從Fred數列中找出稱為Mary的最長子序列滿足下列性質:

Mary[0] > Mary[1] < Mary[2] > Mary[3] < ...

Input

輸入資料的第一列有一個整數T表示測試資料的組數,T最大為50,接著有T組測試資料。每組測試資料一列,該列的第一個整數 n 表示Fred數列的項數,接下來有 n 個整數依序為數列的每一項,n 最大為30000,項與項之間以一個空白字元隔開,且每組資料的前後不會有多餘的空白字元。

Output

請對每組測試資料輸出最長子序列Mary共有幾項。

Sample Input

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
2
5
3

原文出處

沒有留言:

張貼留言