Xor Maximization

Time limit1sMemory limit256 MB

Summary

Pick a nonempty subset of the given integers so the xor of the chosen numbers is as large as possible.

Level: Medium7 of 10
Topics: Bit manipulation, Greedy
Solved: No attempts yet

Problem

Gunnar uses a different password on every website. Remembering all of them is too hard, so for each site he only remembers the method he used to build the password.

For one very important site he started from a file holding a long list of non-negative integers. Gunnar likes the xor operation $\oplus$ , so he picked some of the numbers in the file and used their xor as the password. On single bits, xor is defined by $0 \oplus 0 = 1 \oplus 1 = 0$ and $0 \oplus 1 = 1 \oplus 0 = 1$ . The xor of two integers is obtained by writing both numbers in binary and taking the xor of the bits in each matching position. For example, the xor of $12 = (1100)_2$ and $5 = (101)_2$ is $9 = (1001)_2$ . When numbers are combined with xor instead of addition, the result is called their xor-sum.

Gunnar chose the subset with the largest xor-sum, and that xor-sum became his password. The chosen subset is not empty. He has forgotten how to find such a subset, so he is asking you for help. He will not tell you which site the password belongs to.

Input

The first line contains the count of numbers in the file, $n$ ( $1 \le n \le 100\,000$ ).

The second line contains $n$ space separated integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^{18}$ ).

Output

Print one line with the largest value that can be obtained by picking a non-empty subset of the list and computing its xor-sum.

Examples3

Example 1
Input
```
3
1 3 5
```
Expected output
```
7
```
Example 2
Input
```
4
2 6 4 8
```
Expected output
```
14
```
Example 3
Input
```
1
1
```
Expected output
```
1
```