CF1418G.Three Occurrences

You are given an array $a$ consisting of $n$ integers. We denote the subarray $a[l..r]$ as the array $[a_l, a_{l + 1}, \dots, a_r]$ ($1 \le l \le r \le n$).

A subarray is considered good if every integer that occurs in this subarray occurs there exactly thrice. For example, the array $[1, 2, 2, 2, 1, 1, 2, 2, 2]$ has three good subarrays:

• $a[1..6] = [1, 2, 2, 2, 1, 1]$;
• $a[2..4] = [2, 2, 2]$;
• $a[7..9] = [2, 2, 2]$.

Calculate the number of good subarrays of the given array $a$.

给你一个由 $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$ 中好子数组的个数。

The first line contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$).

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le n$).

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1$, $a_2$, ..., $a_n$（$1 \le a_i \le n$）。

Print one integer — the number of good subarrays of the array $a$.

输出一个整数——数组 $a$ 中“好”子数组的个数。