Minimum Adjacent Swaps to Sort an Array

Given an array of integers, determine the minimum number of adjacent swaps required to sort the array in ascending order. This value is equivalent to the number of inversions in the array. An inversion is defined as a pair of indices ( (i,j) ) such that ( i < j ) and ( a_i > a_j ). Use an efficient divide and conquer algorithm (like merge sort) to count these inversions.

inputFormat

The input is provided via standard input (stdin). The first line contains an 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 is the minimum number of adjacent swaps required to sort the array.## sample

5
4 3 2 1 5

6