Maximum XOR Subsequence

Given an array of integers, your task is to find the maximum possible XOR of any subsequence (i.e. any subset, not necessarily contiguous) of the array. In other words, you can choose any set of elements from the array and compute their bitwise XOR. The problem can be efficiently solved using a bit manipulation technique similar to Gaussian elimination.

In the underlying algorithm, we process each bit from the most significant to the least significant (i.e. from 31 down to 0) and use a pivot element for each bit to create a basis. This ensures that the XOR combination of the basis elements gives the maximum possible result. You may see expressions like \(1 \ll i\) in the code, which denotes a bit mask for the \(i^{th}\) bit.

inputFormat

The first line contains a single integer \(n\) representing the number of elements in the array.

The second line contains \(n\) space-separated integers.

outputFormat

Output a single integer denoting the maximum XOR value that can be obtained from any subsequence of the array.

3
9 8 5

13