Поликарпу подарили массив \(a\) из \(n\) целых чисел. Ему очень нравятся тройки чисел, поэтому для каждого \(j\) (\(1 \le j \le n - 2\)) он выписал тройку из элементов \([a_j, a_{j + 1}, a_{j + 2}]\).
Поликарп считает пару из троек \(b\) и \(c\) красивой, если они различаются ровно в одной позиции, то есть выполняется одно из следующих условий:
- \(b_1 \ne c_1\) и \(b_2 = c_2\) и \(b_3 = c_3\);
- \(b_1 = c_1\) и \(b_2 \ne c_2\) и \(b_3 = c_3\);
- \(b_1 = c_1\) и \(b_2 = c_2\) и \(b_3 \ne c_3\).
Найдите количество красивых пар троек среди выписанных троек \([a_j, a_{j + 1}, a_{j + 2}]\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество красивых пар троек среди пар вида \([a_j, a_{j + 1}, a_{j + 2}]\).
Обратите внимание, что ответ может не умещаться в 32-битные типы данных.
Примечание
В первом примере \(a = [3, 2, 2, 2, 3]\), Поликарп выпишет следующие тройки:
- \([3, 2, 2]\);
- \([2, 2, 2]\);
- \([2, 2, 3]\).
Красивыми парами являются тройка
\(1\) с тройкой
\(2\) и тройка
\(2\) с тройкой
\(3\).
В третьем примере \(a = [1, 2, 3, 2, 2, 3, 4, 2]\), Поликарп выпишет следующие тройки:
- \([1, 2, 3]\);
- \([2, 3, 2]\);
- \([3, 2, 2]\);
- \([2, 2, 3]\);
- \([2, 3, 4]\);
- \([3, 4, 2]\);
Красивыми парами являются тройка
\(1\) с тройкой
\(4\), тройка
\(2\) с тройкой
\(5\), тройка
\(3\) с тройкой
\(6\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
5
3 2 2 2 3
5
1 2 1 2 1
8
1 2 3 2 2 3 4 2
4
2 1 1 1
8
2 1 1 2 1 1 1 1
7
2 1 1 1 1 1 1
6
2 1 1 1 1 1
5
2 1 1 1 1
|
2
0
3
1
8
4
3
2
|