310688: CF1870E. Another MEX Problem

E. Another MEX Problemtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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

ExampleInput

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

Output

2
6
7
0

Note

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$.

题目大意：
这是一个关于MEX（最小排除数）的问题。给定一个整数数组a，其大小为n。你可以选择给定数组的若干个非重叠子数组（注意，某些元素可能不包含在任何子数组中，这是允许的）。对于每个选定的子数组，计算其元素的MEX值，然后计算所有获得的MEX值的按位异或（XOR）。问能得到的最大按位异或值是多少？

MEX（最小排除数）是一个数组中最小的非负整数，它不属于该数组。例如：
- 数组[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不属于。

输入数据格式：
第一行包含一个整数t（1≤t≤5000）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤5000）——数组a的大小。
每个测试用例的第二行包含n个整数a1, a2, …, an（0≤ai≤n）——数组a。
保证所有测试用例中n的总和不超过5000。

输出数据格式：
对于每个测试用例，输出一个数字——选择的子数组的MEX值的最大可能按位异或。题目大意： 这是一个关于MEX（最小排除数）的问题。给定一个整数数组a，其大小为n。你可以选择给定数组的若干个非重叠子数组（注意，某些元素可能不包含在任何子数组中，这是允许的）。对于每个选定的子数组，计算其元素的MEX值，然后计算所有获得的MEX值的按位异或（XOR）。问能得到的最大按位异或值是多少？ MEX（最小排除数）是一个数组中最小的非负整数，它不属于该数组。例如： - 数组[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不属于。 输入数据格式： 第一行包含一个整数t（1≤t≤5000）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤5000）——数组a的大小。 每个测试用例的第二行包含n个整数a1, a2, …, an（0≤ai≤n）——数组a。 保证所有测试用例中n的总和不超过5000。 输出数据格式： 对于每个测试用例，输出一个数字——选择的子数组的MEX值的最大可能按位异或。