Xor Max

Given an array of N numbers, we wish to choose a contiguous subsequence of the array, so that the bitwise XOR of all chosen numbers is maximum.

Bitwise XOR is defined as follows: every bit in the answer is obtained by applying XOR logic on the corresponding bits of the set of numbers:

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

For example 7, 8, and 5 are XOR-ed as follows. The numbers in binary are the following:
0111
1000
0101
----
1010

So the answer is 10 (in decimal). The same answer can be obtained in C/C++/Java by using the XOR operator, as in 7^8^5.

Input Specification

The first line contains one integer N, the size of the array (1 ≤ N ≤ 100 000). The next line contains integers denoting the elements of the array, separated by a single space (1 ≤ element < 2²¹ = 2 097 152).

Output Specification

Output a single line containing the maximum sum that can be obtained.

Sample Input

1. 5
2. 3 8 2 6 4

download as text file

Output for Sample Input

1. 15

download as text file