三明治

题目描述

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$。求满足以下所有条件的正整数三元组 $(i,j,k)$ 的个数。

$1 \le i \lt j \lt k \le N$,

$A_i = A_k$,

$A_i \neq A_j$。

输入格式

输入按以下格式从标准输入给出。

$N$
$A_1$ $A_2$ $\dots$ $A_N$

输出格式

以整数形式输出答案。

样例

5
1 2 1 3 2

3

以下三个正整数三元组 $(i,j,k)$ 满足条件:

$(i,j,k)=(1,2,3)$

$(i,j,k)=(2,3,5)$

$(i,j,k)=(2,4,5)$

7
1 2 3 4 5 6 7

0

也可能不存在满足条件的正整数三元组 $(i,j,k)$。

13
9 7 11 7 3 8 1 13 11 11 11 6 13

20

数据范围

• $3 \le N \le 3 \times 10^5$
• $1 \le A_i \le N$
• 所有输入值均为整数。