Gozz's Prank
Gozz has decided to play an outrageous prank on poor old Nick. Gozz has given Nick an array, \(A\), that he claims is 'sorted'. But actually, Gozz started with some number of non-decreasing arrays, and then interleaved them to create \(A\). This means that \(A\) may not actually be sorted! Can you write a program to help Nick determine the minimum number of non-decreasing arrays Gozz could have started with? Nick needs the program so he can intimidate Gozz with his deduction skills. As we all know, this is the only way to intimidate Gozz.
The way Gozz interleaves arrays to form \(A\) maintains relative order. For example, if \(B\) were used to form part of \(A\), then \(B\) would be interleaved into \(A\) in such a way that the elements of \(B\) formed a not necessarily consecutive sub-sequence of \(A\). Consider the case where \(A=\{1,3,2,4\}\). Gozz could have started with the arrays \(\{1,2\}\) and \(\{3,4\}\), and interleaved them to create \(A\). There are other ways to create \(A\), but all must use at least 2 interleaved arrays, so the answer is 2.
Input Specification
The first line contains a single integer \(T\) (\(1 \leq T \leq 10\)), the number of test cases. Each test case comprises two lines. The first line contains an integer \(N\) (\(1\leq N \leq 10^5\)), the length of \(A\). The next line contains \(N\) space separated integers, each in the inclusive range from \(0\) to \(10^9\), the elements of \(A\).
Output Specification
For each test case, output a line containing a single integers, the minimum number of arrays Gozz could have started with.
Sample Input
3
3
3 2 1
2
1 2
4
1 3 2 4Sample Output
3
1
2
Comments
I spent way too much time on this.
Would you count [1,2,2,4] as an Ascending Sorted Array? Or are repeated elements not allowed?
The statement has been updated!