25657번 - Add One 다국어

문제

Given $n$ integers $a_1, a_2, \ldots, a_n,ドル you want to perform the following operation exactly $n-1$ times.

• Choose two integers $x$ and $y$ in the sequence, remove them, and add a number with the value $x\oplus y$.

Since this alone is just too boring, you can additionally choose a number and add one to it at any moment. You must perform the add-one operation exactly once.

Eventually, only one number will be left in this sequence, and you need to maximize this remaining number. Print the maximum value of the remaining number.

입력

The first line of the input contains a single integer $n$ (1ドル \le n \le 10^6$).

The next line of the input contains $n$ integers $a_1, a_2, \ldots, a_n$ (0ドル \le a_i < 2^{60}$).

출력

Output a single line containing a single integer: the maximum value of the remaining number.

제한

힌트

In the first example, the optimal strategy is:

• Choose 1ドル$ and 2ドル$: $[\mathbf{1}, \mathbf{2}, 1, 2] \to [1, 2, \mathbf{3}]$
• Choose 1ドル$ and 2ドル$: $[\mathbf{1}, \mathbf{2}, 3] \to [3, \mathbf{3}]$
• Add one to the number 3ドル$: $[\mathbf{3}, 3] \to [3, \mathbf{4}]$
• Choose 3ドル$ and 4ドル$: $[\mathbf{3}, \mathbf{4}] \to [\mathbf{7}]$