该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AT_abc318_e [ABC318E] Sandwiches

题目描述

题意简述

给定一个长度为 $N$ 的序列 $A$。求满足以下条件的三元组 $(i,j,k)$ 的个数。

• $1 \le i < j < k \le N$
• $A_i = A_k$
• $A_i \ne A_j$

输入格式

第一行有一个整数 $N$。

第二行有 $N$ 个整数，第 $i$ 个为 $A_i$。

输出格式

$1$ 个整数，如题意。

样例 1

输入

5
1 2 1 3 2

输出

3

样例 2

输入

7
1 2 3 4 5 6 7

输出

0

样例 3

输入

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$

样例一解释

有 $3$ 个，分别为 $(1,2,1),(2,1,2),(2,3,2)$。