分数: 450 点
问题陈述
给定一个长度为正整数的序列 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.
约束
- 3\leq N\leq 3\times 10^5
- 1\leq A_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
将答案打印为整数。
示例输入 1
5 1 2 1 3 2
示例输出 1
3
以下三个正整数三元组 (i,j,k) 满足条件:
- (i,j,k)=(1,2,3)
- (i,j,k)=(2,3,5)
- (i,j,k)=(2,4,5)
示例输入 2
7 1 2 3 4 5 6 7
示例输出 2
0
可能没有正整数的三元组 (i,j,k) 满足条件。
示例输入 3
13 9 7 11 7 3 8 1 13 11 11 11 6 13
示例输出 3
20