
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? InputThere 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$. OutputFor each test case output one line containing one integer, indicating the minimum number of swaps needed to make the permutation "good". Sample Input2 5 3 5 4 2 1 1 1 Sample Output2 0 HintFor 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 