F - Unfair Nim /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

石の山が N 個あり、i 番目の山には A_i 個の石があります。

これを使って青木君と高橋君が次のようなゲームをしようとしています。

  • 青木君から交互に、次の操作を繰り返す
    • 操作:石の山を 1 つ選び、そこから 1 個以上の石を取り除く
  • 先に操作ができなくなった方の負け

このゲームは、両者が最適に行動する場合、ゲーム開始時の各山の石の個数のみによって、先手必勝か後手必勝かが決まります。

そこで高橋君は、ゲームを始める前に、 1 番目の山から 0 個以上 A_1 個未満の石を 2 番目の山に移すことで、後手の高橋君が必勝となるようにしようとしています。

そのようなことが可能なら移動する石の個数の最小値を、不可能ならかわりに -1 を出力してください。

制約

  • 2 \leq N \leq 300
  • 1 \leq A_i \leq 10^{12}

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 \ldots A_N

出力

移動する石の個数の最小値を出力せよ。不可能ならかわりに -1 を出力せよ。


入力例 1

2
5 3

出力例 1

1

石の移動をしなかった場合、青木君が最初に 1 番目の山から 2 個の石を取り除くと、高橋君はその後どのように行動しても負けてしまいます。

ゲームを始める前に 1 番目の山から 1 個の石を移動して、石の個数を 4,4 とした場合、適切な行動を取ることで、高橋君は必ず勝つことができます。


入力例 2

2
3 5

出力例 2

-1

2 番目の山から 1 番目の山へ石を移すことはできません。


入力例 3

3
1 1 2

出力例 3

-1

1 番目の山のすべての石を移すことはできません。


入力例 4

8
10 9 8 7 6 5 4 3

出力例 4

3

入力例 5

3
4294967297 8589934593 12884901890

出力例 5

1

オーバーフローに注意してください。

Score : 600 points

Problem Statement

There are N piles of stones. The i-th pile has A_i stones.

Aoki and Takahashi are about to use them to play the following game:

  • Starting with Aoki, the two players alternately do the following operation:
    • Operation: Choose one pile of stones, and remove one or more stones from it.
  • When a player is unable to do the operation, he loses, and the other player wins.

When the two players play optimally, there are two possibilities in this game: the player who moves first always wins, or the player who moves second always wins, only depending on the initial number of stones in each pile.

In such a situation, Takahashi, the second player to act, is trying to guarantee his win by moving at least zero and at most (A_1 - 1) stones from the 1-st pile to the 2-nd pile before the game begins.

If this is possible, print the minimum number of stones to move to guarantee his victory; otherwise, print -1 instead.

Constraints

  • 2 \leq N \leq 300
  • 1 \leq A_i \leq 10^{12}

Input

Input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print the minimum number of stones to move to guarantee Takahashi's win; otherwise, print -1 instead.


Sample Input 1

2
5 3

Sample Output 1

1

Without moving stones, if Aoki first removes 2 stones from the 1-st pile, Takahashi cannot win in any way.

If Takahashi moves 1 stone from the 1-st pile to the 2-nd before the game begins so that both piles have 4 stones, Takahashi can always win by properly choosing his actions.


Sample Input 2

2
3 5

Sample Output 2

-1

It is not allowed to move stones from the 2-nd pile to the 1-st.


Sample Input 3

3
1 1 2

Sample Output 3

-1

It is not allowed to move all stones from the 1-st pile.


Sample Input 4

8
10 9 8 7 6 5 4 3

Sample Output 4

3

Sample Input 5

3
4294967297 8589934593 12884901890

Sample Output 5

1

Watch out for overflows.