F. Bitwise Battle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Munna has an array $$$A$$$ of $$$N$$$ integers, where $$$N$$$ is an odd number. He enjoys playing with these integers. Initially, his score is $$$0$$$.

In each turn, as long as the array contains at least three elements, he will perform the following operations:

  • Selects two distinct indices say $$$i$$$ and $$$j$$$.
  • Add $$$(A_i ⊕ A_j)$$$ to his score.
  • Removes both elements $$$A_i$$$ and $$$A_j$$$ from the array.

Now, Munna wants to know the maximum possible value of the final remaining element, under the condition that his final score is odd, assuming he plays optimally.

Input

The first line contains a single integer $$$N (1 \leq N \lt 2⋅10^5)$$$, the number of elements in the array.

The second line contains $$$N$$$ space-separated integers $$$A_1, A_2, \ldots, A_N$$$ $$$(1 \leq A_i \leq 10^9)$$$.

Note: It is guranteed that $$$N$$$ is always odd.

Output

If it's impossible to obtain a final odd score output $$$-1$$$.

Otherwise, output the maximum possible value of the final remaining element in the array.

Examples
Input
5
3 4 7 8 1
Output
8
Input
3
2 2 2
Output
-1
Note

For the first test case:

  • In the first operation, Munna selects $$$i=1$$$, $$$j=2$$$ and adds $$$(3⊕4)=7$$$ to his score. After removing $$$3$$$ and $$$4$$$ the array becomes $$$[7,8,1]$$$.
  • In the second operation, he selects $$$i=1$$$, $$$j=3$$$ and adds $$$(7⊕1)=6$$$ to his score. After removing $$$7$$$ and $$$1$$$ the array becomes $$$[8]$$$.

At this point, only one element remains, and the final score is $$$13$$$, which is odd. The remaining element is $$$8$$$, which is the maximum possible under this condition..

For the second test case:

It can be shown that it is impossible to obtain a final odd score, regardless of the operations performed.