Dancing Tuples

Given an array $A$ of size $n$, find how many tuple $(i, j, k)$ are there such that
$1 ≤ i < j < k ≤ n$ and $A_j ≤ A_i ≤ A_k$.

Input

The first line contains an integer $n$ which represents the length of the array. The second line contains a sequence of n integers $A_i$.

$1≤n≤10^{6}$
$1 ≤ A_i ≤ n$

Output

Print one integer — the number of valid tuples.

Samples

Input	Output
5 4 1 3 5 2	2

Input	Output
6 2 5 3 2 5 6	9

Input	Output
5 1 2 3 4 5	0