Minimum Adjacent Swaps to Sort

You are given an array of integers. Your task is to calculate the minimum number of adjacent swaps required to sort the array in non-decreasing order. This number is exactly the inversion count of the array. In other words, if you denote the number of swaps by \(S\) and the inversion count by \(I\), then:

For example:

• For the array [4, 3, 1, 2], the minimum number of swaps required is 5.
• For the array [3, 2, 1], the minimum number of swaps required is 3.
• For the array [1, 2, 3, 4, 5], no swaps are needed.

Your submission should read the input from standard input (stdin) and write the output to standard output (stdout).

inputFormat

The input consists of two lines.

• The first line contains a single integer \(n\) 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: the minimum number of adjacent swaps required to sort the array in non-decreasing order.

4
4 3 1 2

5