Round Table
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: math

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 format:
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 format:
For each test case, print the minimum number of swaps necessary to achieve the desired order.

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

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.

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

Example output:
1
10
22

Editorial:
Main assumption
After playing a bit with the second sample test case one can notice that there are many sequences of swaps of the same length that achieve the same result, and as long as we always swap two people such that the person with a larger number is on the left before the swap, then we always achieve the goal in the minimum number of swaps.
Let us first construct a solution which relies on this assumption, and then prove that the assumption is correct. We need to find any way to arrive at the given permutation from the initial one such that in each swap the person with a larger number is on the left, and count the number of swaps needed efficiently.
Algorithm
We will construct our permutation in steps. After the $$$i$$$-th step, the people with numbers from $$$1$$$ to $$$i$$$ will be in the correct circular order, and the people with numbers from $$$i+1$$$ to $$$n$$$ will be sitting in the order of their numbers directly to the right of person $$$i$$$.
In the starting arrangement the condition above is already satisfied for $$$i=2$$$, since there is just one circular order for two people.
To perform the $$$(i+1)$$$-th step, we need to do the following: person $$$i+1$$$ is currently sitting to the right of person $$$i$$$, but they need to be sitting to the right of some other person $$$j_i$$$ which is determined as the closest person on the left of person $$$i+1$$$ that has a number between $$$1$$$ and $$$i$$$.
Since we cannot move the person $$$i+1$$$ to the left, as we cannot swap person $$$i$$$ and person $$$i+1$$$, the only way to achieve this is by moving person $$$i+1$$$ to the right. But we can't do this directly because person $$$i+2$$$ is there, so what we are going to do is move the entire block of people from $$$i+1$$$ to $$$n$$$ to the right.
Moving the block of people from $$$i+1$$$ to $$$n$$$ by one position to the right takes $$$n-i$$$ swaps, and we need to do this $$$d_i$$$ times where $$$d_i$$$ is the circular distance from person $$$i$$$ to person $$$j_i$$$ when going to the right, and only considering people with numbers from $$$1$$$ to $$$i$$$.
The total number of swaps can therefore be computed as $$$\displaystyle f(p)=\sum_{i=2}^{n-1}d_i(n-i)$$$. The numbers $$$d_i$$$ can be computed using a standard data structure such as a segment tree, a Fenwick tree, or a balanced search tree in $$$\mathcal O(n\log n)$$$.
Proof of the main assumption
Now we need to repay our debts and prove the assumption. It suffices to prove the following.
Lemma. If a permutation $$$q$$$ differs from a permutation $$$p$$$ in only one swap of adjacent elements $$$a$$$ (on the left) and $$$b$$$ (on the right) such that $$$a>b$$$, then $$$f(q)-f(p)=1$$$, where $$$f(p)$$$ is the number of operations used by the above algorithm.
Proof. Indeed, almost all terms in $$$f(p)$$$ and $$$f(q)$$$ sums will be the same. Which terms are going to differ? The quantity $$$d_{a-1}$$$ will increase by $$$1$$$, since the person $$$a$$$ will now need to travel one more step to the right to overtake $$$b$$$. Conversely, $$$d_a$$$ will decrease by $$$1$$$, since the person $$$a+1$$$ will now need to travel one less step to the right as they will have already overtaken $$$b$$$ earlier. All other values of $$$d_i$$$ will stay unchanged. So $$$f(q)-f(p)=(n-(a-1))-(n-a)=1$$$. $$$\blacksquare$$$
By applying the lemma in reverse, we can also see that performing a swap where the largest element is on the right will decrease $$$f(p)$$$ by $$$1$$$. So every swap either increases or decreases $$$f(p)$$$ by $$$1$$$, and $$$f(\mathrm{id})=0$$$ ($$$\mathrm{id}$$$ stands for the identity permutation), therefore $$$f(p)$$$ is indeed the smallest number of swaps needed to reach permutation $$$p$$$, and it does not matter in which order we make the swaps as long as we always make swaps where the person with a larger number is on the left.
Parting words
This problem was inspired by the following paper, where you can learn more about this setup: Abram, Antoine, Nathan Chapelier-Laget, and Christophe Reutenauer. "An Order on Circular Permutations." The Electronic Journal of Combinatorics (2021): P3-31.
The paper also mentions that this setup was used for USAMO 2010, Problem 2. We hope that none of the participants have seen the paper or the USAMO problem before.
We found it quite remarkable that the answer is $$$\mathcal O(n^3)$$$ in magnitude but the order of swaps does not matter, just like in the non-circular problem without any restrictions on swaps where one would simply count the number of inversions in a permutation. We hope you enjoyed solving this problem, too!