D. ПалиндроМЕХ
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юсеф дал вам массив $$$a$$$ из $$$2n$$$ целых чисел. Каждое целое число $$$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}$$$ (minimum excludant) массива целых чисел определяется как наименьшее неотрицательное целое число, которое не встречается в массиве. Например:

  • $$$\operatorname{mex}$$$ массива $$$[2,2,1]$$$ равен $$$0$$$, потому что $$$0$$$ не принадлежит массиву.
  • $$$\operatorname{mex}$$$ массива $$$[3,1,0,1]$$$ равен $$$2$$$, потому что $$$0$$$ и $$$1$$$ принадлежат массиву, а $$$2$$$ — нет.
  • $$$\operatorname{mex}$$$ массива $$$[0,3,1,2]$$$ равен $$$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$$$.