Minimum Adjacent Swaps to Sort

You are given a sequence of n integers. Your task is to determine the minimum number of adjacent swaps required to sort the list in non-decreasing order. An adjacent swap is defined as swapping the positions of two consecutive elements. It can be shown that for any permutation, the minimum number of adjacent swaps required to fully sort the list is equal to the number of inversions in the list. In mathematical terms, if your list is \(a_1, a_2, \dots, a_n\), then the answer is:

\(\sum_{1 \le i a_j]\)

where \([P]\) is 1 if the condition \(P\) is true, and 0 otherwise.

This problem requires efficient computation of this inversion count, and can be solved using a modified merge sort technique in \(O(n \log n)\) time.

inputFormat

The first line of input contains an integer n (\(1 \leq n \leq 10^5\)) representing the number of elements in the list. The second line contains n space-separated integers which form the list.

outputFormat

Output a single integer, the minimum number of adjacent swaps required to sort the list.

## sample

5
4 3 2 1 5

6

</p>