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 non-decreasing order. This number is equivalent to the number of inversions in the array, where an inversion is a pair of indices \( (i,j) \) such that \( i a[j] \).

An efficient solution with a time complexity of \( O(n \log n) \) can be achieved by modifying the merge sort algorithm to count inversions.

Example:

Input:
4
4 3 2 1
Output:
6

</p>

The input consists of two lines. The first line gives the number of elements \( N \), and the second line contains \( N \) space-separated integers. The output is a single integer representing the minimum number of adjacent swaps required to sort the array.

inputFormat

The first line contains an integer \( N \) (where \( 1 \leq N \leq 10^5 \)), the number of elements in the array. The second line contains \( N \) space-separated integers representing the array.

outputFormat

A single integer— the minimum number of adjacent swaps required to sort the array.

## sample

4
4 3 2 1

6

</p>