ZOJ Problem Set - 4046
A permutation $p_1, p_2, \dots, p_N$ of $1, 2, \dots, N$ is called "good", if and only if for all $1 \le i < N$, at least one of the following condition is satisfied.
Given a permutation $p_1, p_2, \dots p_N$ of $1, 2, \dots, N$, each time you can choose two adjancent integers and swap them. How many swaps do you need at least to make the permutation a "good" one?
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:
The first line contains an integer $N$ ($1 \le N \le 10^5$), indicating the length of the permutation.
The second line contains $N$ integers $p_1, p_2, \dots, p_N$ ($1 \le p_i \le N$), indicating the given permutation.
It's guaranteed that the sum of $N$ in all test cases will not exceed $10^6$.
For each test case output one line containing one integer, indicating the minimum number of swaps needed to make the permutation "good".
2 5 3 5 4 2 1 1 1
For the first sample test case, we can change "3 5 4 2 1" to "3 4 5 2 1" first, then change it to "3 4 5 1 2" which is a good permutation.
Author: LIU, Rui
Source: ZOJ Monthly, June 2018