Problems
Number of inversions
Number of inversions
Write a program that finds for a given array A = <a[1]
, a[2]
, ..., a[n]
> the number of such pairs (i, j) that i < j and a[i]
> a[j]
.
Input data
The first line contains the number of array elements n (1 ≤ n ≤ 50000). Second line contains n different elements of array A - nonnegative integers, not greater than 10^6
.
Output data
Print the number of required pairs.
Examples
Input example #1
5 6 11 18 28 31
Output example #1
0
Input example #2
6 4 7 3 5 2 1
Output example #2
12