Counting Inversions

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 determine the total number of inversions in the array.

Definition: The number of inversions in an array is given by the formula:

[ \text{Inversions} = #{(i,j) \mid 0 \le i < j < n \text{ and } A[i] > A[j]} ]

This problem can be efficiently solved using a modified merge sort algorithm with a time complexity of \( O(n \log n) \).

inputFormat

The input consists of two lines:

• The first line contains a single integer \( n \), the number of elements in the array.
• The second line contains \( n \) integers separated by spaces representing the elements of the array.

outputFormat

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

5
2 4 1 3 5

3