Number of inversions
Very easy
Execution time limit is 1 second
Runtime memory usage limit is 128 megabytes
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
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
Print the number of required pairs.
Examples
Input #1
Answer #1
Input #2
Answer #2
Submissions 2K
Acceptance rate 35%