問題文

ここ数日で門松列に関する問題が頻出しております．
ここでは演習を通じて，門松列に対する理解を深め，門松列の問題が出題された時に解けるようになっておきましょう．
門松列対策講座を受講される皆様は既にご存知かと思いますが，門松列とは $3$ 個の要素からなる数列 $a,b,c$ で以下の $2$ つの条件を満たすものです．
・$a,b,c$ は全て異なる
・$3$ つの要素の中で $b$ が最も大きい，または，$b$ が最も小さい

さて，友紀さんは $N$ 要素の整数列 $A_1,A_2,\ldots,A_N$ を持っています．
友紀さんはこの配列の部分列として，門松列が何箇所出現するかを知りたいと思っています．
門松列の数を求めるプログラムを書いてください．
つまり，以下の条件を満たす整数の $3$ つ組 $(i,j,k)$ の数を求めるプログラムを書いてください．
・$1 \leq i < j < k \leq N$ かつ $A_i,A_j,A_k$ が門松列

入力

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

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

出力

答えを $1$ 行で出力してください．

サンプル

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