codeforces#P1974C. Beautiful Triple Pairs
Beautiful Triple Pairs
Description
Polycarp was given an array $a$ of $n$ integers. He really likes triples of numbers, so for each $j$ ($1 \le j \le n - 2$) he wrote down a triple of elements $[a_j, a_{j + 1}, a_{j + 2}]$.
Polycarp considers a pair of triples $b$ and $c$ beautiful if they differ in exactly one position, that is, one of the following conditions is satisfied:
- $b_1 \ne c_1$ and $b_2 = c_2$ and $b_3 = c_3$;
- $b_1 = c_1$ and $b_2 \ne c_2$ and $b_3 = c_3$;
- $b_1 = c_1$ and $b_2 = c_2$ and $b_3 \ne c_3$.
Find the number of beautiful pairs of triples among the written triples $[a_j, a_{j + 1}, a_{j + 2}]$.
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the length of the array $a$.
The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the elements of the array.
It is guaranteed that the sum of the values of $n$ for all test cases in the test does not exceed $2 \cdot 10^5$.
For each test case, output a single integer — the number of beautiful pairs of triples among the pairs of the form $[a_j, a_{j + 1}, a_{j + 2}]$.
Note that the answer may not fit into 32-bit data types.
Input
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the length of the array $a$.
The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the elements of the array.
It is guaranteed that the sum of the values of $n$ for all test cases in the test does not exceed $2 \cdot 10^5$.
Output
For each test case, output a single integer — the number of beautiful pairs of triples among the pairs of the form $[a_j, a_{j + 1}, a_{j + 2}]$.
Note that the answer may not fit into 32-bit data types.
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
Note
In the first example, $a = [3, 2, 2, 2, 3]$, Polycarp will write the following triples:
- $[3, 2, 2]$;
- $[2, 2, 2]$;
- $[2, 2, 3]$.
In the third example, $a = [1, 2, 3, 2, 2, 3, 4, 2]$, Polycarp will write the following triples:
- $[1, 2, 3]$;
- $[2, 3, 2]$;
- $[3, 2, 2]$;
- $[2, 2, 3]$;
- $[2, 3, 4]$;
- $[3, 4, 2]$;