V

問題文

長さ $N$ の数列 $A$ について、$a_i = a_k,a_i > a_j (1 \leq i < j < k \leq N)$ を満たすような $(i,j,k)$ の組の個数を求めよ。

制約

• $3 \leq N \leq 5 \times 10^3$
• $-10^9 \leq a_i \leq 10^9 (1 \leq i \leq N)$

入力

入力はすべて整数である。

N
a_1 a_2 ... a_N

出力

条件を満たす$(i,j,k)$ の組の個数を一行に出力せよ。

サンプル

5
7 4 2 6 7

3

例えば $(i,j,k) = (1,2,5)$ のときは $a_i = a_k = 7, a_i > a_j = 4$ より条件を満たします。 他にも $(i,j,k) = (1,3,5),(1,4,5)$ のときに条件を満たします。この他に条件を満たす $(i,j,k)$ の組はないので、$3$ を出力します。

7
9 8 9 6 8 5 6

3