267. Fewest Swaps to Sort

Challenge1000 ms256 MBSolved by 0%

Print the minimum number of swaps needed to sort n integers into non-decreasing order. Any two positions may be swapped, not only adjacent ones.

Note how different this is from counting inversions, which counts ADJACENT swaps. Reversing 4 3 2 1 needs six adjacent swaps and only two arbitrary ones: exchange the ends, then exchange the middle pair.

Work out where every value has to end up, and the array becomes a set of cycles. A cycle of length k costs k - 1 swaps, because each swap puts one value home and the last one falls into place for free.

Constraints - `1 ≤ n ≤ 200000` - `-1000000000 ≤ a[i] ≤ 1000000000`

Input

The first line contains an integer n. The second line contains n integers.

Output

Print one integer, the minimum number of swaps.

Input4 4 3 2 1

Output2

Noteneeds six ADJACENT swaps and only two arbitrary ones

Input3 1 2 3

Output0

Noteis already sorted

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution