题目描述

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"、"aba"、"abccba" 都是回文串，但是 "codeforces"、"reality"、"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$。

由 ChatGPT 5 翻译

来源

Codeforces 2227D，英文题名 Palindromex。