OpenKattis
Problem Set 1 [converted from problem group]

Start

2018-12-30 15:00 AKST

Problem Set 1 [converted from problem group]

End

2019-12-30 15:00 AKST
The end is near!
Session is over.
Not yet started.
Session is starting in -758 days 14:43:01

Time elapsed

8760:00:00

Time remaining

0:00:00

Problem C
Mega Inversions

The $n^2$ upper bound for any sorting algorithm is easy to obtain: just take two elements that are misplaced with respect to each other and swap them. Conrad conceived an algorithm that proceeds by taking not two, but three misplaced elements. That is, take three elements $a_{i} > a_{j} > a_{k}$ with $i < j < k$ and place them in order $a_{k},a_{j},a_{i}$. Now if for the original algorithm the steps are bounded by the maximum number of inversions $\frac{n(n-1)}{2}$, Conrad is at his wits’ end as to the upper bound for such triples in a given sequence. He asks you to write a program that counts the number of such triples.

Input

The first line of the input is the length of the sequence, $1 \leq n \leq 10^5$. The next line contains the integer sequence $a_{1},a_{2},\ldots ,a_{n}$. You can assume that all $a_{i} \in [1, n]$.

Output

Output the number of inverted triples.

Sample Input 1 Sample Output 1
3
1 2 3
0
Sample Input 2 Sample Output 2
4
3 3 2 1
2