← 返回题目列表

Codeforces · 1454/C

C. 序列变换

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

给定一个序列 $$$a$$$,最初由 $$$n$$$ 整数组成。

您想要转换此序列,以便其中的所有元素都相等(即,它包含同一元素的多次出现)。

要实现此目的,您选择一些在 $$$a$$$ 中至少出现一次的整数 $$$x$$$,然后执行以下操作任意次数(可能为零):选择序列的某个段 $$$[l, r]$$$ 并将其删除。但有一个例外:您不能选择包含 $$$x$$$ 的段。更正式地说,您选择一些连续的子序列 $$$[a_l, a_{l + 1}, \dots, a_r]$$$ 使得 $$$a_i \ne x$$$ if $$$l \le i \le r$$$ ,并将其删除。删除后,已删除段右侧的元素编号会发生变化:第 $$$(r+1)$$$ 个元素现在是第 $$$l$$$ 个元素,第 $$$(r+2)$$$ 个元素现在是第 $$$(l+1)$$$ 个元素,依此类推(即剩余序列刚刚折叠)。

请注意,选择$$$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_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。

保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。

输出

对于每个测试用例,打印答案 - 按照问题陈述中描述的方式转换给定序列所需的最少操作数。可以证明,总是可以执行有限的操作序列,因此序列可以按所需的方式进行转换。

示例

输入 #1

5
3
1 1 1
5
1 2 3 4 5
5
1 2 3 2 1
7
1 2 3 1 2 3 1
11
2 2 1 2 3 2 1 2 3 1 2

输出 #1

0
1
1
2
3