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

5
4 1 3 5 2 

2

6
2 5 3 2 5 6 

9

5
1 2 3 4 5 

0