← 返回题目列表

Codeforces · 2033/C

C. 樱子的实地考察

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

即使在大学,学生也需要放松。这就是樱子老师决定去实地考察的原因。众所周知,所有学生都会排成一排。索引为 $$$i$$$ 的学生有一些感兴趣的主题,被描述为 $$$a_i$$$。作为一名老师,您希望尽量减少学生排队的干扰。

线路的干扰度定义为具有相同兴趣主题的相邻人员的数量。换句话说,干扰是满足 $$$a_j = a_{j + 1}$$$ 的索引 $$$j$$$ ($$$1 \le j < n$$$) 的数量。

为此,您可以选择索引 $$$i$$$ ($$$1\le i\le n$$$) 并交换位置 $$$i$$$ 和 $$$n-i+1$$$ 的学生。您可以执行任意次数的交换。

您的任务是确定通过执行上述操作任意次数可以获得的最小干扰量。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。

每个测试用例由两行描述。

- 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 学生行的长度。
- 第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1\le a_i\le n$$$) — 行中学生感兴趣的主题。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出您可以实现的最小可能的线路干扰。

示例

输入 #1

9
5
1 1 1 2 3
6
2 1 2 2 1 1
4
1 2 1 1
6
2 1 1 2 2 4
4
2 1 2 3
6
1 2 2 1 2 1
5
4 5 5 1 5
7
1 4 3 5 1 1 3
7
3 1 3 2 2 3 3

输出 #1

1
2
1
0
0
1
1
0
2

注意

在第一个示例中,需要对 $$$i=2$$$ 进行运算,因此数组将变为 $$$[1, \textbf{2}, 1, \textbf{1}, 3]$$$,其中粗体元素表示交换了位置的元素。该阵列的扰动等于$$$1$$$。

在第四个示例中,只需对 $$$i=3$$$ 进行运算即可,因此数组将变为 $$$[2, 1, \textbf{2}, \textbf{1}, 2, 4]$$$。该阵列的扰动等于$$$0$$$。

在第八个示例中,只需对 $$$i=3$$$ 进行运算即可,因此数组将变为 $$$[1, 4, \textbf{1}, 5, \textbf{3}, 1, 3]$$$。该阵列的扰动等于$$$0$$$。