Count Inversions in an Array

You are given an array of n integers. An inversion is a pair of indices \((i, j)\) such that \(i a_j\). Your task is to compute the number of inversions in the array using a modified merge sort algorithm.

The problem requires you to implement an efficient algorithm that runs in \(O(n \log n)\) time. In other words, count how many pairs \((i, j)\) satisfy the condition where the earlier element is greater than the later element.

Input/Output Format is described below. Good luck!

inputFormat

The first line of the input contains a single integer (n) (the size of the array). The second line contains (n) space-separated integers representing the array.

outputFormat

Output a single integer, the number of inversions in the array.## sample

5
2 4 1 3 5

3