Minimum Splits for Sorted Unique Subsequences

You are given an array of integers. Your task is to calculate the minimum number of splits required to partition the array into contiguous subsequences such that each subsequence is sorted in non-decreasing order and every element in that subsequence is unique. In other words, when iterating through each element of the array, if you encounter an element that is either a duplicate with respect to the current subsequence or is smaller than the previous element of the subsequence, you must start a new subsequence. The answer is the number of these subsequences.

Formally, let (a_1, a_2, \ldots, a_n) be the given sequence. We want to find the smallest integer (k) and indices (i_1 = 1, i_2, \ldots, i_{k+1} = n+1) such that for each segment (a_{i_j}, a_{i_j+1}, \ldots, a_{i_{j+1}-1}):

(a_{i_j} \leq a_{i_j+1} \leq \cdots \leq a_{i_{j+1}-1}) and all elements are distinct.

Your program should read input from standard input and output the result for each test case to standard output.

inputFormat

The first line of input contains a single integer (T) denoting the number of test cases. Each test case is given on one or more lines: the first number of each test case is an integer (n) representing the number of elements in the array. Then (n) integers follow on the same line (or the next line) representing the elements of the array.

outputFormat

For each test case, output a single line with an integer representing the minimum number of splits required.## sample

5
5 1 2 3 4 5
4 2 1 3 4
6 4 5 5 4 3 2
1 42
6 1 3 2 4 6 5

1
2
5
1
3