Description

Given an array with length n a₁, a₂, ... , a_n. Answer the number of pairs (i, j) satisfying:

• 1 <= i < j <= n
• a_i > a_j

Input

The first line contains one integer n, the length of array. 

The next line contains n integers a₁, a₂, ... , a_n.

Constrain

• 1 <= n <= 10⁶
• | a_i | <= 10¹⁶, i = 1, 2, ... , n

Output

Output one integer, the number of pairs that satisfy the condition above.

Remember to print a ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss