Three Occurrences

现在我给你一个由 $n$ 个整数组成的数组 $a$ ，我们表示子数组 $a[l\dots 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$ 中有多少个好子数组。

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 $ .

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 $ ).

Print one integer — the number of good subarrays of the array $ 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