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(n1)}{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
