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]
.
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
.
Print the number of required pairs.