Minimum Adjacent Swap Operations to Sort an Array

You are given an array of n integers. In one operation, you can swap two adjacent elements. The goal is to sort the array in non-decreasing order using the minimum number of such swap operations.

This problem is equivalent to counting the number of inversions in the array. An inversion is a pair of indices i and j such that i < j and array[i] > array[j]. It can be shown that the minimum number of adjacent swaps required to sort the array is equal to the total number of inversions.

Note: The input will be read from stdin and the output must be printed to stdout.

inputFormat

The first line of input contains an integer n (1 ≤ n ≤ 10^5), denoting the number of elements in the array. The next line contains n space-separated integers, where each integer is between -10^9 and 10^9.

outputFormat

Output a single integer — the minimum number of adjacent swap operations required to sort the array in non-decreasing order.

5
4 3 1 2 5

5