Count Inversions in an Array

You are given an array of unique integers. An inversion in the array is a pair of indices \( (i, j) \) such that \( i a_j \). Your task is to compute the total number of inversions in the given array.

Example: For the array [2, 4, 1, 3, 5], the inversions are (2,1), (4,1) and (4,3) (using 1-indexed positions), hence the answer is 3.

You are advised to use an efficient algorithm based on a modified merge sort to avoid timeout issues on large inputs.

inputFormat

The input is read from standard input (stdin). The first line contains an integer ( n ) representing the number of elements in the array. If ( n ) is greater than 0, the second line contains ( n ) space-separated integers representing the array elements. If ( n ) is 0, no second line is provided.

outputFormat

Output a single integer to standard output (stdout) — the number of inversions in the array.## sample

5
2 4 1 3 5

3