Maximum XOR Subset

You are given an integer n and a sequence of n integers \(a_1, a_2, \dots, a_n\) (which may contain duplicates). Your task is to choose an arbitrary subset (possibly empty) of these numbers such that the XOR sum of the chosen numbers is maximized.

The XOR operation is defined as \(\oplus\) and for any two integers \(x\) and \(y\), \(x \oplus y\) is the bitwise XOR of \(x\) and \(y\). In particular, note that the XOR sum of an empty subset is 0.

Hint: Use the concept of a linear basis (also known as Gaussian elimination in \(\mathbb{F}_2\)) to solve the problem efficiently.

inputFormat

The first line contains an integer n (the number of integers).

The second line contains n space-separated integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single integer, the maximum XOR sum obtainable by choosing a subset of the given numbers.

sample

3
1 2 3

3