SWAPDIFF1 - Difference One Swaps

no tags 

You are given an array of size $N$ containing the integers $1, 2, \ldots, N$ in some order.

A move consists of swapping the integers $k$ and $k+1$ for some $1 \le k \lt N$. In other words, you may swap any pair of integers that has a difference of one.

Find the minimum number of moves required to sort the given array in ascending order.

Input

The first line contains $T$ ($1 \le T \le 1000$), the number of test cases.

Each test case contains $N$ ($2 \le N \le 10^5$) followed by $N$ distinct integers ($1 \le x_i \le N$).

The sum of $N$ over all test cases will not exceed $10^5$.

Output

For each test case, output the number of moves required to sort the array.

Example

Input:
5
2 1 2
2 2 1
3 3 2 1
4 4 2 3 1
6 2 1 4 3 6 5

Output:
0
1
3
5
3

Note

Below is one optimal sequence of moves that sorts [4,2,3,1].

  • Swap 1 and 2: [4,2,3,1] → [4,1,3,2].
  • Swap 2 and 3: [4,1,3,2] → [4,1,2,3].
  • Swap 3 and 4: [4,1,2,3] → [3,1,2,4].
  • Swap 2 and 3: [3,1,2,4] → [2,1,3,4].
  • Swap 1 and 2: [2,1,3,4] → [1,2,3,4].

hide comments
wisfaq: 2018-04-24 21:55:42

Nice problem!


Added by:traxex
Date:2018-04-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem