SWAPDIFF1 - Difference One Swaps
You are given an array of size containing the integers in some order.
A move consists of swapping the integers and for some . 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 (), the number of test cases.
Each test case contains () followed by distinct integers ().
The sum of over all test cases will not exceed .
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 |