E. Очередная задача на MEX
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел $$$a$$$ размера $$$n$$$. Вы можете выбрать некое множество непересекающихся подотрезков данного массива (заметим, что некоторые элементы могут не попасть ни в один из отрезков, это не запрещено), для каждого выбранного подотрезка посчитать MEX его элементов, а затем посчитать побитовое исключающее ИЛИ (XOR) всех полученных значений MEX. Какое наибольшее значение XOR может получиться?

MEX (minimum excluded, минимальное отсутствующее) массива — это наименьшее целое неотрицательное целое число, которое не принадлежит массиву. Например:

  • MEX массива $$$[2,2,1]$$$ равен $$$0$$$, потому что $$$0$$$ не принадлежит массиву.
  • MEX массива $$$[3,1,0,1]$$$ равен $$$2$$$, потому что $$$0$$$ и $$$1$$$ принадлежат массиву, а $$$2$$$ — нет.
  • MEX массива $$$[0,3,1,2]$$$ равен $$$4$$$, потому что $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ принадлежат массиву, а $$$4$$$ — нет.
Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \leq n \leq 5000$$$) — размер массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$) — массив $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5000$$$.

Выходные данные

На каждый набор входных данных выведите одно число — наибольший возможный XOR значений MEX элементов выбранных отрезков.

Пример
Входные данные
4
2
1 0
10
1 2 0 7 1 2 0 2 4 3
10
2 1 0 7 1 2 0 2 4 3
3
1 2 1
Выходные данные
2
6
7
0
Примечание

В первом наборе входных данных максимальный XOR равен $$$2$$$, если взять весь массив, $$$\operatorname{MEX}([1, 0]) = 2$$$.

Во втором наборе входных данных максимальный XOR равен $$$6$$$, если выделить отрезки $$$[1, 2, 0]$$$ и $$$[7, 1, 2, 0, 2, 4, 3]$$$:

  • $$$\operatorname{MEX}([1, 2, 0]) = 3$$$,
  • $$$\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$$$,
таким образом, побитовое исключающее ИЛИ равно $$$5 \oplus 3=6$$$.

В третьем наборе входных данных максимальный XOR равен $$$7$$$, если выделить отрезки $$$[1, 0]$$$ и $$$[7, 1, 2, 0, 2, 4, 3]$$$:

  • $$$\operatorname{MEX}([1, 0]) = 2$$$,
  • $$$\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$$$,
таким образом, побитовое исключающее ИЛИ равно $$$5 \oplus 2 = 7$$$.