311359: CF1974C. Beautiful Triple Pairs

C. Beautiful Triple Pairstime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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}]$.

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.

ExampleInput

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

Output

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:

1. $[3, 2, 2]$;
2. $[2, 2, 2]$;
3. $[2, 2, 3]$.

The beautiful pairs are triple $1$ with triple $2$ and triple $2$ with triple $3$.

In the third example, $a = [1, 2, 3, 2, 2, 3, 4, 2]$, Polycarp will write the following triples:

1. $[1, 2, 3]$;
2. $[2, 3, 2]$;
3. $[3, 2, 2]$;
4. $[2, 2, 3]$;
5. $[2, 3, 4]$;
6. $[3, 4, 2]$;

The beautiful pairs are triple $1$ with triple $4$, triple $2$ with triple $5$, and triple $3$ with triple $6$.

题目大意：
Polycarp得到了一个由n个整数组成的数组a。他非常喜欢三元组数字，所以他写下了每个j（1≤j≤n−2）对应的三元组元素[a_j, a_{j+1}, a_{j+2}]。

如果两个三元组b和c有且仅有一个位置不同，则称这样的三元组对是“美丽”的，具体来说，满足以下条件之一：
- b_1 ≠ c_1 且 b_2 = c_2 且 b_3 = c_3
- b_1 = c_1 且 b_2 ≠ c_2 且 b_3 = c_3
- b_1 = c_1 且 b_2 = c_2 且 b_3 ≠ c_3

要求找出所有写下的三元组[a_j, a_{j+1}, a_{j+2}]中“美丽”的三元组对的数量。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
- 每个测试用例的第一行包含一个整数n（3≤n≤2×10^5）——数组a的长度。
- 每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^6）——数组的元素。
- 保证所有测试用例中n的值之和不超过2×10^5。

输出：
- 对于每个测试用例，输出一个整数——形式为[a_j, a_{j+1}, a_{j+2}]的“美丽”三元组对的数量。
- 注意答案可能不适合32位数据类型。题目大意： Polycarp得到了一个由n个整数组成的数组a。他非常喜欢三元组数字，所以他写下了每个j（1≤j≤n−2）对应的三元组元素[a_j, a_{j+1}, a_{j+2}]。 如果两个三元组b和c有且仅有一个位置不同，则称这样的三元组对是“美丽”的，具体来说，满足以下条件之一： - b_1 ≠ c_1 且 b_2 = c_2 且 b_3 = c_3 - b_1 = c_1 且 b_2 ≠ c_2 且 b_3 = c_3 - b_1 = c_1 且 b_2 = c_2 且 b_3 ≠ c_3 要求找出所有写下的三元组[a_j, a_{j+1}, a_{j+2}]中“美丽”的三元组对的数量。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 - 每个测试用例的第一行包含一个整数n（3≤n≤2×10^5）——数组a的长度。 - 每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^6）——数组的元素。 - 保证所有测试用例中n的值之和不超过2×10^5。 输出： - 对于每个测试用例，输出一个整数——形式为[a_j, a_{j+1}, a_{j+2}]的“美丽”三元组对的数量。 - 注意答案可能不适合32位数据类型。