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.
Output
For each test case, print the minimum number of swaps necessary to achieve the desired order.
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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
2 3 1 4
5
5 4 3 2 1
7
4 1 6 5 3 7 2
|
1
10
22
|