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
For example 7, 8, and 5 are XOR-ed as follows. The numbers in binary are the following:
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.
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 < 221 = 2 097 152).
Output a single line containing the maximum sum that can be obtained.
Output for Sample Input
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|