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.

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 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 |