Minimum Adjacent Swaps to Sort

You are given an array of integers and you need to determine the minimum number of adjacent swap operations required to sort the array in non-decreasing order. In each swap operation, you can only swap two consecutive elements. Formally, given an array \(A = [a_1, a_2, \dots, a_n]\), your task is to sort the array so that \(a_1 \le a_2 \le \dots \le a_n\) using the minimum number of adjacent swaps.

Example:

Input: 5
       4 3 2 1 5
Output: 6

One way to understand the process is by simulating the Bubble Sort algorithm and counting the number of swaps performed. Note that the optimal number of adjacent swaps is equivalent to the number of inversions in the array.

inputFormat

The input is given via standard input. The first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers which represent the elements of the array.

For example:

5
4 3 2 1 5

outputFormat

Output a single integer which is the minimum number of adjacent swaps needed to sort the array in non-decreasing order. The output is printed to standard output.

For example:

6

## sample

5
4 3 2 1 5

6