C. Grouping Increasestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a of size n. You will do the following process to calculate your penalty:   Split array a into two (possibly empty) subsequences^\dagger s and t such that every element of a is either in s or t^\ddagger.  For an array b of size m, define the penalty p(b) of an array b as the number of indices i between 1 and m - 1 where b_i < b_{i + 1}.  The total penalty you will receive is p(s) + p(t). If you perform the above process optimally, find the minimum possible penalty you will receive.^\dagger A sequence x is a subsequence of a sequence y if x can be obtained from y by the deletion of several (possibly, zero or all) elements.^\ddagger Some valid ways to split array a=[3,1,4,1,5] into (s,t) are ([3,4,1,5],[1]), ([1,1],[3,4,5]) and ([\,],[3,1,4,1,5]) while some invalid ways to split a are ([3,4,5],[1]), ([3,1,4,1],[1,5]) and ([1,3,4],[5,1]).InputEach test contains multiple test cases. The first line contains a single integer t (1 \leq t \leq 10^4) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer n (1\le n\le 2\cdot 10^5) — the size of the array a.The second line contains n integers a_1, a_2, \ldots, a_n (1 \le a_i \le n) — the elements of the array a.It is guaranteed that the sum of n over all test cases does not exceed 2\cdot 10^5.OutputFor each test case, output a single integer representing the minimum possible penalty you will receive.ExampleInput
551 2 3 4 588 2 3 1 1 7 4 353 3 3 3 31122 1Output
3
1
0
0
0
NoteIn the first test case, a possible way to split a is s=[2,4,5] and t=[1,3]. The penalty is p(s)+p(t)=2 + 1 =3.In the second test case, a possible way to split a is s=[8,3,1] and t=[2,1,7,4,3]. The penalty is p(s)+p(t)=0 + 1 =1.In the third test case, a possible way to split a is s=[\,] and t=[3,3,3,3,3]. The penalty is p(s)+p(t)=0 + 0 =0.
551 2 3 4 588 2 3 1 1 7 4 353 3 3 3 31122 1
3 1 0 0 0 
['data structures', 'dp', 'greedy', '*1400']