Complaint Sort

The upper bound on the number of swaps a sorting algorithm needs is $n^2$, which is easy to prove. Consider picking two out-of-order elements — a pair with $i < j$ but $a_i > a_j$ — and swapping their positions. Such an out-of-order pair is called an inversion, and there are at most $n(n-1)/2$ inversions.

Hyeonju is a child with many complaints about the world. He is unhappy even about picking just two elements when sorting. Instead, he picks three elements with $i < j < k$ and $a_i > a_j > a_k$, and rewrites their positions in the order $a_k, a_j, a_i$.

Hyeonju named this method the complaint sort algorithm and now wants to find its upper bound. Write a program that counts how many triples of elements Hyeonju can pick — that is, count the number of index triples $(i, j, k)$ with $i < j < k$ and $a_i > a_j > a_k$.

The first line contains the length $n$ of the sequence. ($1 \le n \le 10^5$)

The second line contains the elements of the sequence separated by spaces. Each element is an integer between $1$ and $n$, inclusive.

Print, on the first line, the number of index triples $(i, j, k)$ that satisfy $i < j < k$ and $a_i > a_j > a_k$.