codeforces#P1870E. Another MEX Problem
Another MEX Problem
Description
You are given an array of integers of size . 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 is , because does not belong to the array.
- The MEX of is , because and belong to the array, but does not.
- The MEX of is , because , , and belong to the array, but does not.
The first line contains an integer () — 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 () — the size of the array .
The second line of each test case contains integers () — the array .
It is guaranteed that the sum of all values across all test cases does not exceed .
For each test case, output a single number — the maximum possible XOR of the MEX values of the selected subarrays.
Input
The first line contains an integer () — 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 () — the size of the array .
The second line of each test case contains integers () — the array .
It is guaranteed that the sum of all values across all test cases does not exceed .
Output
For each test case, output a single number — the maximum possible XOR of the MEX values of the selected subarrays.
Note
In the first test case, the maximum XOR is if we take the entire array, .
In the second test case, the maximum XOR is if we partition the array into segments and :
- ,
- ,
In the third test case, the maximum XOR is if we partition the array into segments and :
- ,
- ,