CF2227D.Palindromex

Yousef has given you an array $a$ of $2n$ integers. Every integer $x \in [0, n - 1]$ appears exactly twice in the array.

Your task is to find a subarray $a_l, a_{l + 1}, \dots, a_r$ that is a palindrome$^{\text{∗}}$ such that its $\operatorname{mex}(a_l, a_{l + 1}, \dots, a_r)$$^{\text{†}}$ is maximized. Output this maximum possible value.

$^{\text{∗}}$A palindrome is a string that reads the same backward as forward, for example strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not.

$^{\text{†}}$The $\operatorname{mex}$ (minimum excludant) of an array of integers is defined as the smallest non-negative integer which does not occur in the array. For example:

• The $\operatorname{mex}$ of $[2,2,1]$ is $0$, because $0$ does not belong to the array.
• The $\operatorname{mex}$ of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
• The $\operatorname{mex}$ of $[0,3,1,2]$ is $4$, because $0$, $1$, $2$ and $3$ belong to the array, but $4$ does not.

优素福给了你一个包含 $2n$ 个整数的数组 $a$。对于每个整数 $x \in [0, n - 1]$，它在数组中恰好出现两次。

你的任务是找出一个回文子数组 $a_l, a_{l + 1}, \dots, a_r$，使得其 $\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$ 不在。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$).

The second line of each test case contains $2n$ integers $a_1, a_2, \dots, a_{2n}$ ($0 \le a_i \le n-1$). It is guaranteed that every integer in the range $[0, n-1]$ appears exactly twice.

It is guaranteed that the sum of $2n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, output a single integer — the maximum $\operatorname{mex}$ of any palindromic subarray.

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

In the first test case, the only optimal subarray to choose is $a[1, 8] = [1, 2, 0, 3, 3, 0, 2, 1]$, which is palindromic and has a $\operatorname{mex}$ of $4$.

In the second test case, one of the optimal subarrays to choose is $a[2, 4] = [1, 0, 1]$, which is palindromic and has a $\operatorname{mex}$ of $2$.

In the third test case, we can choose $a[3, 3] = [0]$, which is palindromic and has a $\operatorname{mex}$ of $1$. No other palindromic subarray has a $\operatorname{mex}$ greater than $1$.

在第一个测试用例中，唯一最优的可选子数组是 $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$。