CF1792C.Min Max Sort

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 \lt p_2 \lt \dots \lt p_n$).

给你一个长度为 $n$ 的排列 $p$（长度为 $n$ 的排列是指一个长度为 $n$ 的数组，其中恰好包含从 $1$ 到 $n$ 的每个整数各一次）。

你可以执行以下操作任意多次（包括零次）：

1. 选择两个不同的元素 $x$ 和 $y$，并将它们从排列中删除；
2. 将 $\min(x, y)$ 插入排列中，使其成为第一个元素；
3. 将 $\max(x, y)$ 插入排列中，使其成为最后一个元素。

例如，若 $p = [1, 5, 4, 2, 3]$，且我们对元素 $3$ 和 $5$ 执行该操作，则操作第一步后排列变为 $p = [1, 4, 2]$；插入元素后，排列变为 $p = [3, 1, 4, 2, 5]$。

你的任务是计算使排列 $p$ 按升序排列（即变换 $p$ 使得 $p_1 \lt p_2 \lt \dots \lt p_n$）所需的上述操作的最少次数。

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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 排列中元素的个数。

每个测试用例的第二行包含 $n$ 个互不相同的整数，取值范围为 $1$ 到 $n$ —— 给定的排列 $p$。

所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

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

对于每个测试用例，输出一个整数——将数组 $p$ 按升序排序所需的上述操作的最少次数。

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]$.

在第一个例子中，你可以按如下步骤进行：

1. 在排列 $p = [1, 5, 4, 2, 3]$ 中，选择元素 $4$ 和 $2$，应用操作后，排列变为 $p = [2, 1, 5, 3, 4]$；
2. 在排列 $p = [2, 1, 5, 3, 4]$ 中，选择元素 $1$ 和 $5$，应用操作后，排列变为 $p = [1, 2, 3, 4, 5]$。