A15052 | Round Table

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

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.