CF1662E.Round Table

There are $n$ people, numbered from $1$ to $n$, sitting at a round table. Person $i+1$ is sitting to the right of person $i$ (with person $1$ sitting to the right of person $n$).

You have come up with a better seating arrangement, which is given as a permutation $p_1, p_2, \dots, p_n$. More specifically, you want to change the seats of the people so that at the end person $p_{i+1}$ is sitting to the right of person $p_i$ (with person $p_1$ sitting to the right of person $p_n$). Notice that for each seating arrangement there are $n$ permutations that describe it (which can be obtained by rotations).

In order to achieve that, you can swap two people sitting at adjacent places; but there is a catch: for all $1 \le x \le n-1$ you cannot swap person $x$ and person $x+1$ (notice that you can swap person $n$ and person $1$). What is the minimum number of swaps necessary? It can be proven that any arrangement can be achieved.

有 $n$ 个人，编号为 $1$ 到 $n$，围坐在一张圆桌旁。其中，第 $i+1$ 号人坐在第 $i$ 号人的右侧（第 $1$ 号人坐在第 $n$ 号人的右侧）。

你设计了一种更优的座位安排，该安排由一个排列 $p_1, p_2, \dots, p_n$ 给出。具体而言，你希望通过对人员座位进行调整，使得最终第 $p_{i+1}$ 号人坐在第 $p_i$ 号人的右侧（第 $p_1$ 号人坐在第 $p_n$ 号人的右侧）。注意：对任意一种座位安排，均有 $n$ 个不同的排列可描述它（这些排列彼此可通过旋转得到）。

为实现该目标，你每次只能交换相邻座位上的两个人；但有一个限制：对所有满足 $1 \le x \le n-1$ 的 $x$，你不能交换第 $x$ 号人与第 $x+1$ 号人（注意：你可以交换第 $n$ 号人与第 $1$ 号人）。问：达成目标所需的最少交换次数是多少？可以证明，任意一种座位安排均能实现。

Each test contains multiple test cases. The first line contains an integer $t$ ($1\le t\le 10\,000$) — the number of test cases. The descriptions of the $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($3 \le n \le 200\,000$) — the number of people sitting at the table.

The second line contains $n$ distinct integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i \ne p_j$ for $i \ne j$) — the desired final order of the people around the table.

The sum of the values of $n$ over all test cases does not exceed $200\,000$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1\le t\le 10\,000$），表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 200\,000$），表示围坐在桌旁的人数。

第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$，且当 $i \ne j$ 时 $p_i \ne p_j$），表示人们绕桌就座的期望最终顺序。

所有测试用例中 $n$ 的值之和不超过 $200\,000$。

For each test case, print the minimum number of swaps necessary to achieve the desired order.

对于每个测试用例，输出达到目标顺序所需的最少交换次数。

In the first test case, we can swap person $4$ and person $1$ (who are adjacent) in the initial configuration and get the order $[4, 2, 3, 1]$ which is equivalent to the desired one. Hence in this case a single swap is sufficient.

在第一个测试用例中，我们可以在初始排列中交换相邻的人 $4$ 和人 $1$，从而得到排列 $[4, 2, 3, 1]$，该排列与目标排列等价。因此，在本例中，一次交换即足够。