Sandwiches

题目描述

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

1\leq i < j < k\leq N, $A_i = A_k$, $A_i \neq A_j$。

输入格式

输入按下列格式由标准输入提供： $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出一个整数，表示答案。

5
1 2 1 3 2

3

7
1 2 3 4 5 6 7

0

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

20

提示

$3\leq N\leq 3\times 10^5$ $1\leq A_i \leq N$ 所有输入值均为整数。以下三组满足条件的正整数三元组 $(i,j,k)$：

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

标签: AtCoder|abc318E

来源

AtCoder|abc318E