SWAPDIFF1 - Difference One Swaps
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
offamitkumar:
2020-06-22 15:51:45
Same solution as ***CNT. Just find rest 3 characters and do copy paste. |
|
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 |