Inversion Count

Statement

An inversion is a pair of positions i < j with a[i] > a[j]. Given an array of n integers, count its inversions. Equal values do not form an inversion.

Input

The first line has n. The second line has n integers.

Output

Print one integer: the number of inversions.

Constraints

1 <= n <= 200000
|a_i| <= 10^9
The answer can exceed 32 bits.

Example 1

5
2 4 1 3 5

3

The inversions are (2,1), (4,1) and (4,3).

Example 2

3
3 3 3

0

Equal values are not inversions.