267. Fewest Swaps to Sort
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.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.