Round Table

2000ms

262144K

Description:

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.

Input:

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

Output:

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

Sample Input:

3
4
2 3 1 4
5
5 4 3 2 1
7
4 1 6 5 3 7 2

Sample Output:

1
10
22

Note:

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.

Informação

Provedor Codeforces

Código CF1662E