Count Inversions in an Array

Given an array of integers, your task is to count the number of inversions in the array. An inversion is defined as a pair of indices ( (i, j) ) such that ( i < j ) and ( arr[i] > arr[j] ). This can be mathematically represented as:

[ \text{Number of Inversions} = #{ (i, j) \mid i < j \text{ and } arr[i] > arr[j] } ]

A modified merge sort algorithm can efficiently solve this problem with a time complexity of ( O(n \log n) ). Input is read from standard input and the result is output to standard output.

inputFormat

The first line of input contains an integer ( n ), the number of elements in the array. The second line contains ( n ) space-separated integers representing the array elements.

outputFormat

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

4
8 4 2 1

6