G. Three Occurrencestime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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).OutputPrint one integer — the number of good subarrays of the array a.ExamplesInput
9
1 2 2 2 1 1 2 2 2
Output
3
Input
10
1 2 3 4 1 2 3 1 2 3
Output
0
Input
12
1 2 3 4 3 4 2 1 3 4 2 1
Output
1

9
1 2 2 2 1 1 2 2 2

3 
['data structures', 'divide and conquer', 'hashing', 'two pointers', '*2500']