← 返回题目列表

Codeforces · 2227/D

D. 回文

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

Yousef 给了你一个由 $$$2n$$$ 整数组成的数组 $$$a$$$。每个整数 $$$x \in [0, n - 1]$$$ 出现 正好两次 数组中的 。

你的任务是找到一个子数组 $$$a_l, a_{l + 1}, \dots, a_r$$$ ,它是一个回文$$$^{\text{*}}$$$,使得它的 $$$\operatorname{mex}(a_l, a_{l + 1}, \dots, a_r)$$$$$$^{\text{†}}$$$ 最大化。输出这个最大可能值。

$$$^{\text{*}}$$$回文是向后读与向前读相同的字符串,例如字符串 “z”, “aaa”, “阿巴”, “abccba” 是回文,但是字符串 “代码力量”, “现实”, “ab” 不是。

$$$^{\text{†}}$$$整数数组的$$$\operatorname{mex}$$$(最小排除数)被定义为数组中不出现的最小非负整数。例如:

  • $$$[2,2,1]$$$ 的 $$$\operatorname{mex}$$$ 是 $$$0$$$,因为 $$$0$$$ 不属于该数组。
  • $$$[3,1,0,1]$$$ 的 $$$\operatorname{mex}$$$ 是 $$$2$$$,因为 $$$0$$$ 和 $$$1$$$ 属于数组,但 $$$2$$$ 不属于数组。
  • $$$[0,3,1,2]$$$ 的 $$$\operatorname{mex}$$$ 是 $$$4$$$,因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 属于该数组,但 $$$4$$$ 不属于该数组。

输入

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

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

每个测试用例的第二行包含 $$$2n$$$ 整数 $$$a_1, a_2, \dots, a_{2n}$$$ ($$$0 \le a_i \le n-1$$$)。保证 $$$[0, n-1]$$$ 范围内的每个整数恰好出现两次。

保证所有测试用例的 $$$2n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 任何回文子数组的最大 $$$\operatorname{mex}$$$。

示例

输入
复制

6
4
1 2 0 3 3 0 2 1
2
0 1 0 1
2
1 1 0 0
3
2 0 2 1 1 0
4
0 1 3 0 3 1 2 2
3
0 1 2 1 0 2

输出
复制

4
2
1
1
2
3

注意

在第一个测试用例中,唯一要选择的最佳子数组是 $$$a[1, 8] = [1, 2, 0, 3, 3, 0, 2, 1]$$$,它是回文,并且 $$$\operatorname{mex}$$$ 为 $$$4$$$。

在第二个测试用例中,要选择的最佳子数组之一是 $$$a[2, 4] = [1, 0, 1]$$$,它是回文数组,并且 $$$\operatorname{mex}$$$ 为 $$$2$$$。

在第三个测试用例中,我们可以选择 $$$a[3, 3] = [0]$$$,它是回文,并且 $$$\operatorname{mex}$$$ 为 $$$1$$$。没有其他回文子数组的 $$$\operatorname{mex}$$$ 大于 $$$1$$$。