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.
```