Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4046
Good Permutation

Time Limit: 1 Second      Memory Limit: 65536 KB

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.

  • $p_i + 1 = p_{i+1}$

  • $p_i = N$ and $p_{i+1} = 1$

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?

Input

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

Output

For each test case output one line containing one integer, indicating the minimum number of swaps needed to make the permutation "good".

Sample Input

2
5
3 5 4 2 1
1
1

Sample Output

2
0

Hint

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
Submit    Status