Minimum Adjacent Swaps to Sort an Array

You are given an array of n integers. Your task is to determine the minimum number of adjacent swaps required to sort the array in ascending order.

This problem can be solved efficiently by counting the number of inversions in the array. An inversion is a pair of indices i < j such that a[i] > a[j]. The number of inversions gives the exact number of adjacent swaps needed if only adjacent swaps are allowed.

You are expected to implement an algorithm (commonly via a modified merge sort) that runs in O(n log n) time.

Hint: Use the formula \( \text{swaps} = \text{number of inversions} \).

inputFormat

The first line contains a single integer n (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

Output a single integer, the minimum number of adjacent swaps required to sort the array in ascending order.

## sample

3
3 1 2

2

</p>