Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Dancing Tuples

By Aashiq · Limits 3s, 512 MB

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

InputOutput
5
4 1 3 5 2

2

InputOutput
6
2 5 3 2 5 6

9

InputOutput
5
1 2 3 4 5

0


Statistics

100% Solution Ratio