CF1974C Beautiful Triple Pairs

题目描述

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

输入 #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]$。

美丽的三元组对为三元组 $1$ 与三元组 $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]$。

美丽的三元组对为三元组 $1$ 与三元组 $4$，三元组 $2$ 与三元组 $5$，以及三元组 $3$ 与三元组 $6$。

由 ChatGPT 4.1 翻译