# 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