Count Inversions

Given an array a of n integers, an inversion is a pair of indices \((i, j)\) such that \(1 \le i < j \le n\) and \(a[i] > a[j]\). Mathematically, we wish to compute

\[ \text{inversions} = \# \{ (i,j) \mid 1 \le i a[j] \} \]

This is a classic problem that can be solved efficiently using a modified merge sort algorithm.

inputFormat

The input consists of two lines. 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.

outputFormat

Output a single integer denoting the number of inversions in the array.

## sample

5
2 3 8 6 1

5

</p>