题目描述

本题译自 eJOI2022 Problem A. Adjacent Pairs

如果对于任意满足 $1\le i\le 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\le i\le n)$ 和一个数字 $x\ (1\le x\le 10^9)$。然后将 $x$ 赋给 $a_i$。在此操作后，数组必须仍然是好的。

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

输入格式

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

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

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

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

输出格式

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

2
5
4 5 2 4 5
2
1 2

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$。

评分

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

子任务编号	附加限制	分值
$1$	$\sum n\le 100$	$20$
$2$	$\sum n\le 500$	$10$
$3$	$\sum n\le 4\cdot 10^3$	$25$
$4$	无附加限制	$45$

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