Minimum Adjacent Swaps to Sort

You are given a list of integers representing the heights of flower pots. The goal is to determine the minimum number of adjacent swaps required to arrange the list in non-decreasing order.

Mathematically, if you have an array \(a_1, a_2, \dots, a_n\), you need to compute the minimum number of swaps (where only adjacent elements can be swapped) such that the resulting list is sorted in non-decreasing order. It can be shown that this number is equal to the number of inversions in the list, i.e., the number of pairs \((i,j)\) such that \(i a_j\).

Example: For the input array [5, 1, 3, 2, 4], the number of inversions (and hence the minimum number of adjacent swaps) is 5.

inputFormat

The input is given via standard input (stdin) and has the following format:

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), denoting the number of flower pots.
The second line contains \(n\) space-separated integers representing the heights of the flower pots.

outputFormat

Output a single integer to standard output (stdout), which is the minimum number of adjacent swaps required to sort the flower pots in non-decreasing order.

5
5 1 3 2 4

5