Count Inversions

You are given an array of integers. An inversion is defined as a pair of indices \( (i, j) \) such that \( i A[j] \). Your task is to count the total number of inversions in the array.

Note: Try to design an algorithm with a time complexity of \( O(n \log n) \), for example by implementing a modified merge sort.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \( n \) which represents the number of elements in the array. The second line contains \( n \) space-separated integers.

outputFormat

Output a single integer representing the total number of inversions in the array on standard output (stdout).

5
1 3 2 3 1

4