Minimum Adjacent Swaps to Sort Array

Given an array of integers, determine the minimum number of adjacent swaps required to sort the array in non-decreasing order. An adjacent swap operation exchanges two neighboring elements.

The number of required swaps is equivalent to the number of inversions in the array. An inversion is defined as a pair \( (i, j) \) where \( i A[j] \).

You are encouraged to use an efficient algorithm such as merge sort to count the inversions with a time complexity of \( O(n \log n) \).

inputFormat

The first line contains an integer \( n \) (\( 1 \leq n \leq 10^5 \)), representing the number of elements in the array.

The second line contains \( n \) space-separated integers representing the array elements.

outputFormat

Output a single integer representing the minimum number of adjacent swaps required to sort the array in non-decreasing order.

## sample

3
3 2 1

3

</p>