← 返回题目列表

Codeforces · 1974/C

C. 美丽的三对

中文机器翻译题面 查看原题

Polycarp 被赋予了一个由 $$$n$$$ 整数组成的数组 $$$a$$$。他非常喜欢三元组的数字,因此对于每个 $$$j$$$ ($$$1 \le j \le n - 2$$$),他写下了一个三元组元素 $$$[a_j, a_{j + 1}, a_{j + 2}]$$$。

Polycarp 认为一对三元组 $$$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 位数据类型。

示例

输入 #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

输出 #1

2
0
3
1
8
4
3
2

注意

在第一个例子中,$$$a = [3, 2, 2, 2, 3]$$$,Polycarp 将写出以下三元组:

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

在第三个例子中,$$$a = [1, 2, 3, 2, 2, 3, 4, 2]$$$,Polycarp 将写出以下三元组:

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