← 返回题目列表

AtCoder · abc318_e

H. 三明治

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

分数: 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