Minimum Swaps to Sort

You are given an array of n integers. Your task is to compute the minimum number of swaps required to sort the array in non-decreasing order. A swap is defined as exchanging the positions of two elements. A key observation is that the array can be divided into cycles, and for each cycle of length k, at least \(k-1\) swaps are required to place every element in its correct position.

For example, if there is a cycle of 3 elements, then at least 2 swaps are needed. The overall minimum number of swaps is the sum of \(k-1\) over all cycles.

The input is read from standard input (stdin) and the output is printed to standard output (stdout).

inputFormat

The first line contains a single integer n representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Print a single integer, the minimum number of swaps required to sort the array in non-decreasing order.

5
4 3 1 2 5

3