CF1454C Sequence Transformation

给定一个初始包含 $n$ 个整数的序列 $a$。 你需要将该序列变换为所有元素都相等的序列（即序列中所有元素都相同）。 为此，你可以选择一个在 $a$ 中至少出现一次的整数 $x$，然后可以进行任意次数（可能为零）如下操作：选择序列中的某个区间 $[l, r]$ 并将其删除。但有一个例外：你不能选择包含 $x$ 的区间。更正式地说，你选择一个连续子序列 $[a_l, a_{l+1}, \dots, a_r]$，其中 $a_i \ne x$ 对于所有 $l \le i \le r$，并将其删除。删除后，右侧元素的编号会发生变化：原本第 $(r+1)$ 个元素现在变为第 $l$ 个，原本第 $(r+2)$ 个元素现在变为第 $(l+1)$ 个，依此类推（即剩余的序列会自动收缩）。 注意，选择 $x$ 不是一次操作。同时，你不能删除任何 $x$ 的出现位置。 例如，假设 $n = 6$，$a = [1, 3, 2, 4, 1, 2]$。那么一种两步变换的方法是选择 $x = 1$，然后： 1. 选择 $l = 2$，$r = 4$，此时序列变为 $a = [1, 1, 2]$； 2. 选择 $l = 3$，$r = 3$，此时序列变为 $a = [1, 1]$。 注意，选择 $x$ 并不算一次操作。同时，你不能删除任何 $x$ 的出现位置。 你的任务是求出将序列变换为所有元素都相等所需的最少操作次数。 你需要回答 $t$ 组独立的测试用例。

输入的第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来是 $t$ 组测试用例。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示序列 $a$ 的长度。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示序列 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$）。

对于每个测试用例，输出一个整数，表示将给定序列变换为所有元素都相等所需的最少操作次数。可以保证总能通过有限次操作达到目标。

由 ChatGPT 4.1 翻译