给你一个长度为$$$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]$$$。