← 返回题目列表

AtCoder · past23_h

H. 三明治三元组

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

问题陈述

给你一个整数 N,以及一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N.

A 三明治三重 是一个整数三元组 (i,j,k) 这样:

  • 1\le i < j < k \le N;和
  • A_i=A_k\neq A_j.

三明治三人组有多少个?

约束

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

输入

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

N
A_1 A_2 \ldots A_N

输出

打印答案。


示例输入 1

5
2 5 2 2 5

示例输出 1

4

三明治三元组是 (i,j,k)=(1,2,3),(1,2,4),(2,3,5),(2,4,5).


示例输入 2

5
4 4 4 4 4

示例输出 2

0

没有选择 (i,j,k) 满足 A_i=A_k\neq A_j.


示例输入 3

10
2 2 6 4 4 6 6 2 3 2

示例输出 3

27