C. Min Max Sorttime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a permutation p of length n (a permutation of length n is an array of length n in which each integer from 1 to n occurs exactly once).You can perform the following operation any number of times (possibly zero):   choose two different elements x and y and erase them from the permutation;  insert the minimum of x and y into the permutation in such a way that it becomes the first element;  insert the maximum of x and y into the permutation in such a way that it becomes the last element. For example, if p = [1, 5, 4, 2, 3] and we want to apply the operation to the elements 3 and 5, then after the first step of the operation, the permutation becomes p = [1, 4, 2]; and after we insert the elements, it becomes p = [3, 1, 4, 2, 5].Your task is to calculate the minimum number of operations described above to sort the permutation p in ascending order (i. e. transform p so that p_1 < p_2 < \dots < p_n).InputThe first line contains a single integer t (1 \le t \le 10^4) — the number of test cases.The first line of the test case contains a single integer n (1 \le n \le 2 \cdot 10^5) — the number of elements in the permutation.The second line of the test case contains n distinct integers from 1 to n — the given permutation p.The sum of n over all test cases doesn't exceed 2 \cdot 10^5.OutputFor each test case, output a single integer — the minimum number of operations described above to sort the array p in ascending order.ExampleInput
451 5 4 2 331 2 342 1 4 365 2 4 1 6 3Output
2
0
1
3
NoteIn the first example, you can proceed as follows:   in the permutation p = [1, 5, 4, 2, 3], let's choose the elements 4 and 2, then, after applying the operation, the permutation becomes p = [2, 1, 5, 3, 4];  in the permutation p = [2, 1, 5, 3, 4], let's choose the elements 1 and 5, then, after applying operation, the permutation becomes p = [1, 2, 3, 4, 5]. 
451 5 4 2 331 2 342 1 4 365 2 4 1 6 3
2 0 1 3 
['binary search', 'brute force', 'greedy', 'math', 'two pointers', '*1500']