题目描述

江月诗对回文序列很感兴趣，准备研究一个长度为 $2n$ 的整数数组 $a$。$0,1,\ldots,n-1$ 中的每个整数在数组中都恰好出现两次。

江月诗想在所有非空连续子数组中，找出一个回文子数组，使其 $\operatorname{mex}$ 尽可能大。请你求出这个最大值。

数组 $b$ 是回文的，当且仅当它从左到右与从右到左读到的元素序列相同。例如，$[2]$、$[1,2,1]$、$[0,3,3,0]$ 是回文数组。

数组的 $\operatorname{mex}$ 指其中没有出现的最小非负整数。例如：

$$\operatorname{mex}([2,2,1])=0,\qquad \operatorname{mex}([3,1,0,1])=2,\qquad \operatorname{mex}([0,3,1,2])=4.$$

输入格式

第一行包含一个整数 $t$，表示测试用例数量，满足 $1\le t\le10^4$。

每组测试用例包含两行：第一行为整数 $n$，满足 $1\le n\le10^5$；第二行为 $2n$ 个整数 $a_1,a_2,\ldots,a_{2n}$，满足 $0\le a_i\le n-1$，且每个值恰好出现两次。

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

输出格式

对每组测试用例，输出一个整数，表示所有回文子数组的 $\operatorname{mex}$ 的最大值。

输入输出样例 1

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

提示/说明

第一组测试用例可以选择整个数组，其为回文，且 $\operatorname{mex}=4$。

第二组测试用例可以选择 $a[2,4]=[1,0,1]$，其为回文，且 $\operatorname{mex}=2$。

第三组测试用例可以选择 $a[3,3]=[0]$，得到 $\operatorname{mex}=1$，不存在更大的答案。