bonus

As it would be way too easy to have to solve just $7$ problems in a contest, the scientific committee decided to give you a permutation too. But because we live in the present, we want, from a moral standpoint, to give it further, in a modified version, so that it respects certain properties.

Task

You are given a permutation. Make as few swaps of adjacent values as possible, in such a way that for the final permutation, $|P_i - P_{i-1}| = 1$ for at least $N - 2$ indexes between $2$ and $N$.

Input data

The first line of the input will contain $T$, the number of test cases. Each test case contains on the first line the order of the permutation, $N$ and on the second line the permutation, formed of $N$ distinct values between $1$ and $N$.

Output data

The output will contain $T$ lines, on each line you will print the minimal answer for the corresponding test case.

Constraints and clarifications

• $1 \leq T \leq 5$
• $1 \leq N \leq 50 \ 000$
• For $10$ points, $N \leq 7$
• For $20$ more points, $N \leq 50$
• For $10$ more points, one of the permutations for which we can obtain the minimum number of swaps is the identity permutation $(1, 2, 3, \dots, N)$.
• For $10$ more points, the answer is at most $2$

Example

stdin

5
4
1 2 3 4
4
4 1 2 3
4
2 3 4 1
5
3 2 1 5 4
6
1 2 4 3 5 6

stdout

0
0
0
4
1

Explanation

We have $T = 5$ tests. In the first $3$ tests, the permutations already respect the given property, therefore there is no need of any swaps.

The fourth permutation needs $4$ swaps of adjacent values to be brought to either $1 \ 2 \ 3 \ 4 \ 5$ or $2 \ 3 \ 4 \ 5 \ 1$.

For the fifth permutation it is enough to swap $3$ and $4$ to obtain the identical permutation.