Count Inversions in an Array

You are given an array of N integers. Your task is to count the number of inversions in the array.

An inversion is a pair of indices \( (i, j) \) such that \( i A[j] \). In other words, it is a situation where a larger number precedes a smaller number in the array.

Example:

Input: 5
       2 4 1 3 5
Output: 3
Explanation: The inversions are (2,1), (4,1), and (4,3).

This problem can be efficiently solved by modifying the merge sort algorithm to count the number of inversions while sorting the array.

inputFormat

The input is read from stdin and consists of two lines. The first line contains a single integer (N), the number of elements in the array. The second line contains (N) space-separated integers representing the array (A).

outputFormat

Output a single integer to stdout that represents the number of inversions in the array.## sample

5
2 4 1 3 5

3