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 位数据类型的范围。

在第一个样例中，$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 翻译