It's Mooin' Time II

题目描述

Farmer John 想向 Elsie 描述他最喜欢的一场 USACO 比赛，但她很难理解他为什么这么喜欢。他说：“我最喜欢比赛的一部分是 Bessie 说了句 ‘It's Mooin' Time’，然后在整场比赛里到处 moo。” 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 将一个 moo 定义为一个由三个整数组成的数组，其中第二个整数等于第三个整数，但不等于第一个整数。如果可以从数组中删除一些整数，直到只剩下这个 moo，则称该 moo 在比赛中出现。 由于 Bessie 据称“在整场比赛里到处 moo”，请帮助 Elsie 统计在比赛中出现的不同 moo 的数量！如果两个 moo 不由相同的整数按相同顺序组成，则认为它们不同。

输入格式

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

输出格式

输出在比赛中出现的不同 moo 的数量。 注意：本题涉及的整数可能很大，可能需要使用 64 位整数数据类型（例如 Java 中的 "long"，C/C++ 中的 "long long"）。

6
1 2 3 4 4 4

3

提示

这场比赛有三个不同的 moo：“1 4 4”、“2 4 4” 和 “3 4 4”。 SCORING: Inputs 2-4: $N\le 10^2$ Inputs 5-7: $N\le 10^4$ Inputs 8-11: No additional constraints. Problem credits: Benjamin Qi

标签: USACO|2025|Bronze

来源

USACO|2025|Bronze