该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小明有一个包含 n 个正整数的序列 A，他希望从中挑选出包含三个数的子序列 B，要求 B 中的第 2 个数跟第 3 个数相同，但跟第 1 个数不同，问他可以挑选出多少个不同的子序列 B。

格式要求

输入格式

输入的第一行包含一个整数 n。

接下来一行包含 n 个整数，第 i 个整数表示 Ai。

输出格式

输出共一行，包含一个整数，表示不同的子序列 B 的数量。

样例

7
3 1 2 3 4 1 4

4

样例解释

可以选出不同子序列为：

（3 1 1）、（3 4 4）、 （1 4 4）、（ 2 4 4 ）

数据规模

对于 30% 的数据，n ≤ 100；

对于 60% 的数据，n ≤ 10000；

对于 100% 的数据，n <= 1e6, 1 ≤ Ai ≤ n