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

P11668 [USACO25JAN] It's Mooin' Time II B

题目描述

Farmer John 正在试图向 Elsie 描述他最喜欢的 USACO 竞赛，但她很难理解为什么他这么喜欢它。他说「竞赛中我最喜欢的部分是 Bessie 说 『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。

Elsie 仍然不理解，所以 Farmer John 将竞赛以文本文件形式下载，并试图解释他的意思。竞赛被定义为一个包含 $N$（$1\le N\le 10^6$）个整数的数组 $a_1, a_2, \dots, a_N$（$1\le a_i\le N$）。Farmer John 定义哞叫为一个包含三个整数的数组，其中第二个整数等于第三个整数，但不等于第一个整数。一种哞叫被称为在竞赛中发生，如果可以从数组中移除整数，直到只剩下这一哞叫。

由于 Bessie 据称「在整个竞赛中一直哞哞叫」，请帮助 Elsie 计算竞赛中发生的不同哞叫的数量！两种哞叫是不同的，如果它们并非由相同的整数以相同的顺序组成。

输入格式

输入的第一行包含 $N$。

第二行包含 $N$ 个空格分隔的整数 $a_1,a_2,\dots,a_N$。

输出格式

输出竞赛中发生的不同哞叫的数量。

注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，Java 中的 "long"，C/C++ 中的 "long long"）。

输入输出样例 #1

输入 #1

6
1 2 3 4 4 4

输出 #1

3

说明/提示

样例解释

竞赛包含三种不同的哞叫："1 4 4"，"2 4 4" 和 "3 4 4"。

子任务

• 测试点 2-4：$N\le 10^2$。
• 测试点 5-7：$N\le 10^4$。
• 测试点 8-11：没有额外限制。