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] &gt; a[j] and i &lt; j.

Input Format

A number n, denoting number of elements n number of integers, denoting elements of array

Output Format

Print the count of total inversions

Constraints

1 &lt;= N &lt;= 10^5
1 &lt;= arr[i] &lt;= 10^6

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

5
2 4 1 3 5

Output

Maximize Sum Of Arr[i]*i Of An Array

Find First And Last Postion Of Element In Sorted Array