Problem Statement

Over the past few days, problems about Kadomatsu sequences have been appearing frequently.
Here, let us deepen our understanding of Kadomatsu sequences through practice, so that we can solve Kadomatsu sequence problems whenever they are set.
As those of you taking this Kadomatsu sequence preparation course may already know, a Kadomatsu sequence is a sequence $a,b,c$ consisting of $3$ elements that satisfies the following $2$ conditions.
・$a,b,c$ are all distinct
・Among the $3$ elements, $b$ is the largest, or $b$ is the smallest

Now, Yuki has an integer sequence $A_1,A_2,\ldots,A_N$ of $N$ elements.
Yuki wants to know how many times a Kadomatsu sequence appears as a subsequence of this array.
Write a program that finds the number of Kadomatsu sequences.
That is, write a program that finds the number of $3$-tuples of integers $(i,j,k)$ satisfying the following condition.
・$1 \leq i < j < k \leq N$ and $A_i,A_j,A_k$ is a Kadomatsu sequence

Input

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

$1 \leq N \leq 1000000 = 10^6$
$1 \leq A_k \leq 1000000000 = 10^9$

Output

Output the answer on $1$ line.

Sample

5
1 4 2 5 2

5

2
1 1

0

35
1 3 5 5 4 3 5 5 5 3 3 4 2 5 4 4 3 2 3 1 3 1 5 1 5 1 2 1 5 2 4 1 4 2 1

2015