G. Три вхождения
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$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[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