Minimum Swaps to Sort in Descending Order

You are given an array of n integers. Your task is to determine the minimum number of swaps needed to sort the array in strictly descending order. In one swap, you can exchange any two elements.

One key observation is that the problem can be solved by detecting cycles in the array's permutation relative to the target descending order. For each cycle of length k, the minimum number of swaps required is k − 1. In mathematical terms, if there are cycles with sizes \( c_1, c_2, \dots, c_m \), then the answer is:

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

This is a classical problem that involves sorting and cycle detection.

inputFormat

The first line of input contains an integer n (1 ≤ n ≤ 10⁵), representing the number of elements in the array. The second line contains n space-separated integers representing the array elements.

outputFormat

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

5
1 2 3 4 5

2