Another MEX Problem
Contest: CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2300
Tags: bitmasks, brute force, dp, shortest paths

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 format:
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 format:
For each test case, output a single number — the maximum possible XOR of the MEX values of the selected subarrays.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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

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

Example input:
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

Example output:
2
6
7
0

Editorial:
Let's solve the problem using dynamic programming, let's store $$$dp[i][j]$$$ such that $$$dp[i][j]=1$$$ if it is possible to obtain an $$$XOR$$$ of $$$MEX$$$ values from the prefix up to $$$i$$$ (excluding $$$i$$$) equal to $$$x$$$, and $$$0$$$ otherwise. Notice that the answer cannot be greater than $$$n$$$. Therefore, the size of this two-dimensional array is $$$O(n^2)$$$.
Let's learn how to solve this in $$$O(n^3)$$$:
We iterate over $$$l$$$ from $$$1$$$ to $$$n$$$, and inside that, we iterate over $$$r$$$ from $$$l$$$ to $$$n$$$, maintaining the value $$$x=MEX([a_l, a_{l+1}, \dots, a_r])$$$. Then, for all $$$j$$$ from $$$0$$$ to $$$n$$$, we update $$$dp[r+1][j \oplus x]=1$$$ if $$$dp[l][j]=1$$$. This way, we update based on the case when the resulting set includes the set $$$[a_l, a_{l+1}, \dots, a_r]$$$.
We also need to update if $$$dp[l][x]=1$$$, we assign $$$dp[l+1][x]=1$$$. This accounts for the case when we do not include $$$a_l$$$ in the answer.
Let's define $$$MEX(l, r) = MEX([a_l, a_{l+1}, \dots, a_r])$$$, this will make the following text clearer.
Let's consider the segment $$$l, r$$$. Notice that if there exist $$$l_2$$$ and $$$r_2$$$ ($$$l \leq l_2 \leq r_2 \leq r$$$) such that $$$l_2 \ne l$$$ or $$$r_2 \ne r$$$ and $$$MEX(l, r)=MEX(l_2, r_2)$$$, then we can take the segment $$$l_2, r_2$$$ instead of the segment $$$l, r$$$ in the set of $$$MEX$$$ values, and the answer will remain the same. If, however, there is no such segment $$$l_2, r_2$$$ for the segment $$$l, r$$$, then we call this segment $$$l, r$$$ irreplaceable.
Now let's prove that there are no more than $$$n \cdot 2$$$ irreplaceable segments. For each irreplaceable segment, let's look at the larger element of the pair $$$a_l, a_r$$$, let's assume $$$a_l$$$ is larger (the other case is symmetric). Now, let's prove that there is at most one segment where $$$a_l$$$ is the left element and $$$a_l \leq a_r$$$, by contradiction:
Suppose there are at least 2 such segments, let's call their right boundaries $$$r_1, r_2$$$ ($$$r_1 < r_2$$$). Notice that $$$MEX(l, r_1) > a_l$$$, otherwise the segment $$$l, r_1$$$ would not be irreplaceable (we could remove $$$a_l$$$). Since $$$a_l >= a_{r_2}$$$, then $$$MEX(l, r) > a_{r_2}$$$. It is obvious that $$$a_{r_2}$$$ appears among the elements $$$[a_l, \dots, a_{r_1}]$$$, and therefore $$$MEX(l, r_2-1) = MEX(l, r_2)$$$, which means that the segment $$$l, r_2$$$ is not irreplaceable, contradiction.
For each $$$a_i$$$, there is at most one irreplaceable segment where it is the smaller of the two extremes, and at most one where it is the larger. Therefore, the total number of irreplaceable segments is no more than $$$2 \cdot n$$$.
Let's update the DP only through the irreplaceable segments, then the solution works in $$$O(n^2+n \cdot C)$$$ time, where $$$C$$$ is the number of irreplaceable segments. However, we have already proven that $$$C\leq 2n$$$, so the overall time complexity is $$$O(n^2)$$$.