时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的整数数组 $A$，求有多少个三元组 $(i,j,k)$ 同时满足以下两个条件：

• $i < j < k$
• $A_i=A_j=A_k$

格式

输入格式

第一行包含一个整数 $n$，表示数组长度。

第二行包含 $n$ 个整数，表示数组 $A$。

输出格式

输出一个整数，表示符合条件的三元组的数量。

样例

样例输入 #1

12
4 1 5 4 1 1 4 1 5 4 1 1

样例输出 #1

24

数据规模

对于 $30\%$ 的数据， $n\leq 100$。

另有 $30\%$ 的数据， $-10^6 \leq A_i\leq 10^6$。

对于 $100\%$ 的数据， $3\leq n\leq 10^6$， $-10^9 \leq A_i\leq 10^9$。