Count Inversions
hard
1. Given an array of integers. Find the Inversion Count in the array. 2. For an array, inversion count indicates how far (or close) the array is from being sorted. If array is already sorted then the inversion count is 0. If an array is sorted in the reverse order then the inversion count is the maximum. 3. Formally, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.
Constraints
1 <= N <= 10^5 1 <= arr[i] <= 10^6
Format
Input
A number n, denoting number of elements n number of integers, denoting elements of array
Output
Print the count of total inversions
Example
Sample Input
5
2 4 1 3 5
Sample Output
3
Question Video