Andy recently learned about the bitwise XOR operation in computer class.
One of Andy's friends owns an array ~a~, which has a length of ~N~. Andy wants to make his friend sad by XORing all of the numbers in ~a~ by a non-negative number ~x~ such that the sum of the sums of each subarray is minimal. Since Andy is not an expert at XOR, he asks you to find ~x~ for him. If multiple solutions exist for ~x~, output the smallest one.
Recall subarrays are consecutive subsequences. For example, the subarrays of the array ~[1, 2, 3]~ are ~[1], [2], [3], [1, 2], [2, 3], [1, 2, 3]~. The sum of the sums of each subarray for this array will be ~(1) + (2) + (3) + (1 + 2) + (2 + 3) + (1 + 2 + 3) = 20~.
Constraints
For all subtasks:
~1 \le N \le 2 \times 10^5~
~0 \le a_i \le 10^9~
Subtask 1 [30%]
~0 \le a_i \le 1~
Subtask 2 [70%]
No additional constraints.
Input Specification
The first line contains an integer ~N~.
The second line contains ~N~ integers, his friend's array ~a~.
Output Specification
Output the minimal solution for ~x~, which is the number that Andy wishes to know.
Sample Input 1
3
1 2 3
Sample Output 1
3
Explanation for Sample 1
After XORing by 3, the array becomes ~[2, 1, 0]~. The sum of the sums of each subarray is ~(2) + (1) + (0) + (2 + 1) + (1 + 0) + (2 + 1 + 0) = 10~. It can be shown that ~10~ is the smallest possible sum of the sums of each subarray.
Sample Input 2
7
7 9 10 43 56 2 4
Sample Output 2
10
Comments