CF1418G Three Occurrences

给定一个包含 $n$ 个整数的数组 $a$。我们用 $a[l..r]$ 表示子数组 $[a_l, a_{l + 1}, \dots, a_r]$（$1 \le l \le r \le n$）。 如果一个子数组中出现的每个整数都恰好出现了三次，则称该子数组为“好子数组”。例如，数组 $[1, 2, 2, 2, 1, 1, 2, 2, 2]$ 有三个好子数组： - $a[1..6] = [1, 2, 2, 2, 1, 1]$； - $a[2..4] = [2, 2, 2]$； - $a[7..9] = [2, 2, 2]$。 请计算给定数组 $a$ 的好子数组的数量。

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。

输出一个整数，表示数组 $a$ 的好子数组的数量。

由 ChatGPT 4.1 翻译