Minimum Swaps to Sort Array

Given an array of n distinct integers, determine the minimum number of swaps required to sort the array in ascending order. In one swap, you can exchange any two elements in the array.

The key observation is to decompose the permutation into cycles. For each cycle of length k, the number of swaps required is k - 1. Thus, the total number of swaps is given by:

\( \sum_{i=1}^{m} (\text{cycleSize}_i - 1) \)

where m is the number of cycles.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer n — the number of elements in the array.
• The second line contains n space-separated distinct integers representing the array.

outputFormat

Output a single integer to stdout denoting the minimum number of swaps required to sort the array in ascending order.

4
4 3 1 2

3