Minimum Swaps to Sort the Array

Given an array of n integers, determine the minimum number of swap operations required to transform the array into a non-decreasing (sorted) sequence. This is equivalent to counting the number of inversions in the array. An inversion is a pair of indices i < j such that a[i] > a[j]. The answer is the total count of such inversions.

Mathematical Formulation:

Let the array be A = [a_1, a_2, \dots, a_n]. We need to compute:

[ \text{Inversions}(A) = \sum_{1 \le i < j \le n} \mathbf{1}_{{a_i > a_j}}, ]

where \(\mathbf{1}_{\{a_i > a_j\}}\) is 1 if \(a_i > a_j\) and 0 otherwise.

Example:

• For A = [3, 1, 2], the inversions are: (3,1) and (3,2), so the answer is 2.
• For A = [5, 4, 3, 2, 1], every pair is an inversion resulting in an answer of 10.
• For A = [1, 2, 3, 4], the array is already sorted so the answer is 0.

inputFormat

The input is read from standard input (stdin). The first line contains a single integer n (1 ≤ n ≤ 10⁵), denoting the number of elements in the array. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output to standard output (stdout) a single integer – the minimum number of swap operations (or the inversion count) required to sort the array in non-decreasing order.

## sample

3
3 1 2

2