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}$$$。
示例
输入复制
641 2 0 3 3 0 2 120 1 0 121 1 0 032 0 2 1 1 040 1 3 0 3 1 2 230 1 2 1 0 2
输出复制
421123
注意
在第一个测试用例中,唯一要选择的最佳子数组是 $$$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$$$。