Description

In this quiz, you need to implement inversion pairs count. 

Inversion pair

Let A be a sequence of numbers. (i, j) is an inversion pair if i < j but A[i] > A[j].

For example: A = [1, 2, 3, 4], then A has no inversion pair.

For example: B = [4, 3, 2, 1], B has 6 inversion pairs: (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4).

Inversion pairs count

Output the number of inversion pairs

For example: A = [9, 4, 5, 3], the output is 5. Because A has inversion pairs: (1, 2), (1, 3), (1, 4), (2, 4), (3, 4).

Note

You are allowed to use STL.

But don’t use any STL related to sort.

Input

There are multiple testcases, and each testcase begins with an integer n, indicating the number of elements in the sequence.

The next line includes the n integers in the sequence.

Please note:

1) 1 <= n <= 500000

2) 1 <= value of each element <= 2³¹ - 1

    (each value is integer)

Output

For each input, output the inversion pairs count.

Each output is separated by a newline symbol.

Sample Input  Download

Sample Output  Download

Tags

Discuss