Minimum Swaps to Sort Permutation

You are given a permutation P of the first n natural numbers. Your task is to determine the minimum number of swaps required to sort the permutation in ascending order.

The solution is based on the idea of cycle detection: every cycle of length \(c\) will require \(c-1\) swaps to put the elements in their correct positions. In other words, if the permutation decomposes into cycles with lengths \(c_1, c_2, \dots, c_k\), then the minimum number of swaps is given by:

[ \text{swaps} = \sum_{i=1}^{k} (c_i - 1) ]

Write a program that reads the input from standard input (stdin) and prints the result to standard output (stdout).

inputFormat

The first line contains an integer n, the number of elements in the permutation. The second line contains n space-separated integers representing the permutation.

outputFormat

Output a single integer, the minimum number of swaps required to sort the permutation.

4
4 3 2 1

2