eolymp
bolt
Try our new interface for solving problems
Problems

Number of inversions

Number of inversions

Time limit 1 second
Memory limit 128 MiB

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 (1n50000). 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