CF1870E.Another MEX Problem

You are given an array of integers $a$ of size $n$. You can choose a set of non-overlapping subarrays of the given array (note that some elements may be not included in any subarray, this is allowed). For each selected subarray, calculate the MEX of its elements, and then calculate the bitwise XOR of all the obtained MEX values. What is the maximum bitwise XOR that can be obtained?

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• The MEX of $[2,2,1]$ is $0$, because $0$ does not belong to the array.
• The MEX of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
• The MEX of $[0,3,1,2]$ is $4$, because $0$, $1$, $2$ and $3$ belong to the array, but $4$ does not.

给你一个长度为 $n$ 的整数数组 $a$。你可以从中选择若干个互不重叠的子数组（注意：某些元素可能未被包含在任何子数组中，这是允许的）。对每个选定的子数组，计算其元素的 MEX（最小缺失值），然后计算所有得到的 MEX 值的按位异或。你能获得的最大按位异或值是多少？

数组的 MEX（minimum excluded，最小排除值）是指不属于该数组的最小非负整数。例如：

• $[2,2,1]$ 的 MEX 是 $0$，因为 $0$ 不在数组中。
• $[3,1,0,1]$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 在数组中，但 $2$ 不在。
• $[0,3,1,2]$ 的 MEX 是 $4$，因为 $0$、$1$、$2$ 和 $3$ 都在数组中，但 $4$ 不在。

The first line contains an integer $t$ ($1 \leq t \leq 5000$) — the number of test cases. This is followed by the description of the test cases.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 5000$) — the size of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq n$) — the array $a$.

It is guaranteed that the sum of all $n$ values across all test cases does not exceed $5000$.

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

For each test case, output a single number — the maximum possible XOR of the MEX values of the selected subarrays.

对于每个测试用例，输出一个整数——所选子数组的 MEX 值所能达到的最大异或（XOR）结果。

In the first test case, the maximum XOR is $2$ if we take the entire array, $\operatorname{MEX}([1, 0]) = 2$.

In the second test case, the maximum XOR is $6$ if we partition the array into segments $[1, 2, 0]$ and $[7, 1, 2, 0, 2, 4, 3]$:

• $\operatorname{MEX}([1, 2, 0]) = 3$,
• $\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$,

therefore, the XOR is $5 \oplus 3=6$.

In the third test case, the maximum XOR is $7$ if we partition the array into segments $[1, 0]$ and $[7, 1, 2, 0, 2, 4, 3]$:

• $\operatorname{MEX}([1, 0]) = 2$,
• $\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$,

therefore, the XOR is $5 \oplus 2 = 7$.

在第一个测试用例中，若取整个数组，则最大异或值为 $2$，即 $\operatorname{MEX}([1, 0]) = 2$。

在第二个测试用例中，若将数组划分为子段 $[1, 2, 0]$ 和 $[7, 1, 2, 0, 2, 4, 3]$，则最大异或值为 $6$：

• $\operatorname{MEX}([1, 2, 0]) = 3$，
• $\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$，

因此，异或值为 $5 \oplus 3 = 6$。

在第三个测试用例中，若将数组划分为子段 $[1, 0]$ 和 $[7, 1, 2, 0, 2, 4, 3]$，则最大异或值为 $7$：

• $\operatorname{MEX}([1, 0]) = 2$，
• $\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$，

因此，异或值为 $5 \oplus 2 = 7$。