Min Max Sort
Contest: Educational Codeforces Round 142 (Rated for Div. 2)
Difficulty rating: 1500
Tags: binary search, brute force, greedy, math, two pointers

You 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):

1. choose two different elements $$$x$$$ and $$$y$$$ and erase them from the permutation;
2. insert the minimum of $$$x$$$ and $$$y$$$ into the permutation in such a way that it becomes the first element;
3. 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$$$).

Input format:
The 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$$$.

Output format:
For each test case, output a single integer — the minimum number of operations described above to sort the array $$$p$$$ in ascending order.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, you can proceed as follows:

1. 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]$$$;
2. 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]$$$.

Example input:
4
5
1 5 4 2 3
3
1 2 3
4
2 1 4 3
6
5 2 4 1 6 3

Example output:
2
0
1
3

Editorial:
If the array is already sorted, then the answer is $$$0$$$. Otherwise, there is a last operation, after which the permutation takes the form $$$1, 2, \dots, n$$$. Which means that the elements $$$1$$$ and $$$n$$$ are selected as the last operation (because they are at the first and last positions after the operation). Now we know that the last operation is $$$(1, n)$$$ and it doesn't matter where exactly these numbers are in the permutation, i. e. we can assume that the answer has increased by $$$1$$$, and consider only the numbers $$$2, 3, \dots, n-2, n-$$$1. Similarly, for the "remaining" permutation, there are two options, either it is sorted, and then the answer is $$$1$$$, or there is a last operation and the numbers $$$2$$$ and $$$n-1$$$ are used in it. And so on until the "remaining" permutation is sorted or empty.
It remains to find out how to quickly check whether the numbers in the segment $$$[k, n - k + 1]$$$ are sorted (they go in the correct order in the initial permutation). Note that this segment corresponds to values of elements, not to positions in the permutation. If this segment is sorted for some $$$k$$$, then the answer does not exceed $$$k-1$$$.
There are several ways to check, let's consider one of them. Note that if the segment $$$[k, n - k + 1]$$$ is sorted for some value $$$k$$$, then it will be sorted for large values as well. So we can start with the maximum value of $$$k$$$ (which is equal to $$$\left\lfloor\frac{n+1}{2}\right\rfloor$$$) and decrease it until the segment remains sorted. Now for each $$$k$$$ we need only two checks that $$$pos_k$$$ < $$$pos_{k + 1}$$$ and $$$pos_{n - k + 1}$$$ > $$$pos_{n - (k + 1) + 1}$$$, where $$$pos_i$$$ is the position of the element $$$i$$$ in the permutation.
Thus, we got the solution in linear time.
Another way is to run binary search on $$$k$$$ since if the numbers in $$$[k, n - k + 1]$$$ appear in the permutation in sorted order, the same holds for $$$k+1$$$. This approach yields a solution in $$$O(n \log n)$$$.