← 返回题目列表

Codeforces · 1672/C

C. 不等数组

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

给你一个长度为 $$$n$$$ 的数组 $$$a$$$。我们将数组的相等性定义为索引数量 $$$1 \le i \le n - 1$$$,使得 $$$a_i = a_{i + 1}$$$。我们可以进行以下操作:

- 选择两个整数 $$$i$$$ 和 $$$x$$$,使得 $$$1 \le i \le n - 1$$$ 和 $$$1 \le x \le 10^9$$$。然后,将 $$$a_i$$$ 和 $$$a_{i + 1}$$$ 设置为等于 $$$x$$$。

找到使数组的相等性小于或等于 $$$1$$$ 所需的最少操作数。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10 ^ 5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组的元素。

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

输出

对于每个测试用例,打印所需的最少操作数。

示例

输入 #1

4
5
1 1 1 1 1
5
2 1 1 1 2
6
1 1 2 3 3 4
6
1 2 1 4 5 4

输出 #1

2
1
2
0

注意

在第一个测试用例中,我们可以选择 $$$i=2$$$ 和 $$$x=2$$$ 来组成 $$$[1, 2, 2, 1, 1]$$$。然后,我们可以选择$$$i=3$$$和$$$x=3$$$来组成$$$[1, 2, 3, 3, 1]$$$。

在第二个测试用例中,我们可以选择 $$$i=3$$$ 和 $$$x=100$$$ 来组成 $$$[2, 1, 100, 100, 2]$$$。