Problem Description

Comparing people can be frustrating, but comparing fish can be challenging for the fish themselves. Recently,小鱼 (Little Fish) participated in a "Cuteness Competition" where the cuteness of each fish is evaluated. The participating fish are arranged from left to right, all facing left. Each fish is assigned an integer value representing its cuteness. Clearly, the higher the integer, the cuter the fish, and any two fish may have the same cuteness level. Since all fish are facing left, each fish can only see the cuteness of the fish to its left. They are all calculating how many fish within their sight are less cute than themselves. Please help these cute but not-so-smart fish to compute this.

Unlike previous requirements, the competition committee is interested in the "Total Pride Value" of the arrangement. There are $n$ fish in total, and there are $\frac{n(n+1)}{2}$ different intervals. The pride value of each interval is equal to the number of pairs where the cuteness value of a fish on the left is greater than that of a fish on the right (essentially the number of inverse pairs in the interval). The Total Pride Value is the sum of the "pride values" of all intervals. The task is to output the Total Pride Value.

Input Format

The first line contains an integer $n$, representing the number of fish.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, separated by spaces, representing the cuteness levels of the fish from left to right.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

8
1 9 2 6 0 8 1 7

Sample Output #1

106

Sample Input #2

10
1 10 8 5 6 2 3 9 4 7

Sample Output #2

270

Sample Input #3

20
6 0 4 5 8 8 0 6 6 1 0 4 6 6 0 0 7 2 0 5

Sample Output #3

3481

Notes

For $100\%$ of the data, $n \le 10^6$, $a_i \le 10^9$, and all numbers are non-negative integers.

见题面 Input 部分

见题面 Output 部分