← 返回题目列表

Codeforces · 1969/E

E. 唯一数组

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

给你一个长度为$$$n$$$的整数数组$$$a$$$。 $$$a$$$ 的子数组是其连续子序列之一(即数组 $$$[a_l, a_{l+1}, \dots, a_r]$$$ 对于某些整数 $$$l$$$ 和 $$$r$$$ 使得 $$$1 \le l < r \le n$$$)。如果有一个整数在子数组中只出现一次,我们称该子数组为唯一的。

您可以执行以下操作任意次数(可能为零):选择数组的一个元素并将其替换为任何整数。

你的任务是计算上述操作的最少次数,以使数组 $$$a$$$ 的所有子数组都是唯一的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 为了使数组 $$$a$$$ 的所有子数组都是唯一的上述操作的最小数量。

示例

输入 #1

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

输出 #1

0
2
1
0

注意

在第二个测试用例中,您可以替换 $$$1$$$-st 和 $$$3$$$-rd 元素,例如:$$$[3, 4, 1, 4]$$$。

在第三个测试用例中,您可以替换第 $$$4$$$ 个元素,例如,如下所示:$$$[3, 1, 2, 3, 2]$$$。