Minimum Bubble Sort Swaps

Given an array of integers, compute the minimum number of adjacent swaps required to sort the array in non-decreasing order using the bubble sort method. In bubble sort, only adjacent elements are swapped, and each swap moves one element closer to its sorted position. The total number of swaps is equivalent to the number of inversions in the original array, that is, $$\text{inversions} = \sum_{1 \le i A_j].$$

Example: For the array [4, 3, 1, 2], the minimum number of swaps needed is 5.

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.

outputFormat

Output a single integer which is the minimum number of swaps required to sort the array.

4
4 3 1 2

5