Write a program that finds for a given array A = <a1, a2, ..., an> the number of such pairs (i, j) that i < j and ai > aj.

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 106.

Output

Print the number of required pairs.