Minimum Swaps to Sort

Difficulty: 1500 3000 ms 128 MB

math sorting

The list is a permutation of 1..N. Any two elements may be swapped. What is the minimum number of swaps to sort it ascending?

Input: the first line has N; the second line has a permutation of 1..N.

Output: the minimum number of swaps.

Constraints:

• 1 ≤ N ≤ 10⁵

Sample Tests

5
2 3 4 5 1

4

4
1 2 3 4

0

Read the Editorial