Minimum Adjacent Swaps to Sort

You are given an array of n integers. Your task is to compute the minimum number of adjacent swaps required to sort the array in ascending order. Each swap can only exchange two neighboring elements. It can be shown that this number is equal to the total number of inversions in the array. In other words, if we define an inversion as a pair of indices \( (i,j) \) such that \( i a[j] \), then the answer is the inversion count.

The formula for the inversion count can be represented in \( \LaTeX \) as:

[ \text{Inversions} = \sum_{i=1}^{n} \sum_{j=i+1}^{n} \mathbf{1}_{{a[i] > a[j]}} ]

Solve the problem using an efficient method (for example, a modified merge sort) that counts the inversions.

inputFormat

The input is read from standard input (stdin) and consists of:

• 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.

outputFormat

Output a single integer to standard output (stdout) which represents the minimum number of adjacent swaps required to sort the array.

## sample

3
3 2 1

3

</p>