题目描述

给定一个由 $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$，...，$a_n$（ $1 \le a_i \le n$ ）。

输出格式

输出一个整数——数组 $a$ 的好子数组数量。

9
1 2 2 2 1 1 2 2 2

3

10
1 2 3 4 1 2 3 1 2 3

0

12
1 2 3 4 3 4 2 1 3 4 2 1

1