← 返回题目列表

AtCoder · abc429_c

F. 奇数一个子序列

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个长度的整数序列 N, A=(A_1,A_2,\ldots,A_N).
求整数三元组的个数 (i,j,k) 满意 1\leq i<j<k\leq N 满足以下条件:

恰好包含两个不同的值 A_i,A_j,A_k。也就是说,其中的两个 A_i,A_j,A_k 相等,其余一项不同。

约束

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

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

打印满足条件的整数三元组的数量。


示例输入 1

5
3 2 5 2 2

示例输出 1

6

例如, (i,j,k)=(1,2,4) 满足条件,因为恰好有两个不同的值, 2 和 3,包含在 A_1=3, A_2=2,和 A_4=2.
包括这个在内,六个三元组 (i,j,k)=(1,2,4),(1,2,5),(1,4,5),(2,3,4),(2,3,5),(3,4,5) 满足条件。
因此,打印 6.


示例输入 2

3
1 1 1

示例输出 2

0

可能没有满足条件的三元组。