「eJOI2022」Adjacent Pairs

题目描述

如果对于任意满足 $1 \leq i \leq m-1$ 的 $i$ ，都有 $b_i \neq b_{i+1}$ ，我们就称数组 $b_1, b_2, \ldots, b_m$ 是好的。

给定一个长度为 $n$ 的好数组 $a_1, a_2, \ldots, a_n$ 。你可以对这个数组进行如下操作：

选择任意下标 $i$ ( $1 \leq i \leq n$ ) 和一个数字 $x$ ( $1 \leq x \leq 10^9$ )。然后将 $x$ 赋给 $a_i$ 。在此操作后，数组必须仍然是好的。

你想要进行一些操作，使得最终得到的数组只包含恰好两个不同的值。请确定为了达成目标所需的最小操作次数。

第一行一个整数 $t$ ( $1 \leq t \leq 10^5$ )，表示测试点个数。对于每组测试点的描述如下。

每个测试点的第一行包含一个整数 $n$ ( $2 \leq n \leq 2 \cdot 10^5$ )，表示数组长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq n$ )，表示这个数组。保证对于 $1 \leq i \leq n-1$ ，满足 $a_i \neq a_{i+1}$ （即，这个数组是好的）。

保证一组数据的所有测试点中 $n$ 的总和不超过 $2 \cdot 10^5$ 。

对于每组数据输出一行，表示为了使得最终得到的数组只包含恰好两个不同的值，所需的最小操作次数。

3
0

对于第一个测试点，一种最优的操作序列如下：

$$(4,5,2,4,5) \to (2,5,2,4,5) \to (2,5,2,4,2) \to (2,5,2,5,2) $$

对于第二个测试点，数组已经只包含两个不同值了，因此答案为 $0$ 。

详细子任务附加限制及分值如下表所示。

注： $\sum n$ 指一组测试数据中所有测试点的 $n$ 的总和。