# 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%