Given an array of integers arr[] , if i < j and arr[i] > arr[j] then the pair (i, j) is called an inversion of arr[] . Write a program to find the total number of inversion count in arr[] .

Problem Note

• Inversion Count for an array indicates – how close the array is from being sorted.
• If the array is already sorted then the inversion count is 0.
• We are assuming that all elements are unique.
• If the array is sorted in the reverse order that inversion count is the maximum.

Example 1

Input: arr[] = [4, 1, 3, 2] 
Output: 4 
Explanation: There are four inversions:(4, 1),(4, 3),(4, 2) and (3, 2). 

Example 2

Input: arr[] = [4, 3, 2, 1] 
Output: 6 
Explanation: There are six inversions:(4, 3),(4, 2),(4, 1) ,(3, 2),(3, 1) and (2, 1). 

Example 3

Input: arr[] = [1, 2, 3, 4] 
Output: 0 
Explanation: Array is already sorted.