C. Красивые пары троек
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарпу подарили массив $$$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}]$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — длину массива $$$a$$$.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — элементы массива.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество красивых пар троек среди пар вида $$$[a_j, a_{j + 1}, a_{j + 2}]$$$.

Обратите внимание, что ответ может не умещаться в 32-битные типы данных.

Пример
Входные данные
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
Примечание

В первом примере $$$a = [3, 2, 2, 2, 3]$$$, Поликарп выпишет следующие тройки:

  1. $$$[3, 2, 2]$$$;
  2. $$$[2, 2, 2]$$$;
  3. $$$[2, 2, 3]$$$.
Красивыми парами являются тройка $$$1$$$ с тройкой $$$2$$$ и тройка $$$2$$$ с тройкой $$$3$$$.

В третьем примере $$$a = [1, 2, 3, 2, 2, 3, 4, 2]$$$, Поликарп выпишет следующие тройки:

  1. $$$[1, 2, 3]$$$;
  2. $$$[2, 3, 2]$$$;
  3. $$$[3, 2, 2]$$$;
  4. $$$[2, 2, 3]$$$;
  5. $$$[2, 3, 4]$$$;
  6. $$$[3, 4, 2]$$$;
Красивыми парами являются тройка $$$1$$$ с тройкой $$$4$$$, тройка $$$2$$$ с тройкой $$$5$$$, тройка $$$3$$$ с тройкой $$$6$$$.