Description

Given an array A of integers. Please find the number of pairs <A[i], A[j]> in A that satisfy the following conditions.

1. i < j
2. A[i] > A[j]

For example, we can find that <4,2>, <6,2>, <9,2> satisfy conditions.

Input

Each test case begins with a line containing an integer N, which is the size of the array.

The next line contains N integers, which denote the elements of the array.

Please note:

1. 0 ≤ N ≤ 1,000,000
2. -2³¹ ≤ array element ≤ 2³¹.

Output

Print the number of pairs <A[i], A[j]> in A that satisfy those conditions. A newline is added after the answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss