Description

When people compare with each other, it is annoying; when fish compare with each other, it is even worse. Little Fish recently joined a “cuteness comparison” contest, where the cuteness of each fish is compared. The fish are lined up from left to right, all facing to the left. Then each fish is given an integer value representing its cuteness. Obviously, the larger the integer is, the cuter the fish is, and any two fish may have the same cuteness value. Since all fish face left, each fish can only see the cuteness values of the fish to its left. They are all calculating in their minds: within their view, how many fish are less cute than themselves? Please help these cute little fish, whose brains are not good enough, compute this.

Different from the previous requirement, the organizing committee cares about the “total smugness value” of this arrangement. There are $n$ little fish, and there are $\frac{n(n+1)}2$ different intervals in total. The smugness value of each interval equals the number of pairs in this interval that satisfy “the fish on the left has a larger cuteness value than the fish on the right” (in fact, it is the number of inversions in the interval). The total smugness value is the sum of the smugness values of all intervals. Now you need to output what the “total smugness value” is.

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 of each little fish from left to right.

Output Format

Output one integer representing the answer.

8
1 9 2 6 0 8 1 7

106

10
1 10 8 5 6 2 3 9 4 7

270

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

3481

Hint

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

Translated by ChatGPT 5