Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Назовем подмассивом $$$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$$$.
В первой строке задано одно целое число $$$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
Название |
---|