← 返回题目列表

AtCoder · abc172_f

F. 不公平的尼姆

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有 N 成堆的石头。的 i第一堆有 A_i 石头。

Aoki 和 Takahashi 将使用它们来玩以下游戏:

  • 从青木开始,两名玩家交替进行以下操作:
    • 操作:选择一堆石子,并从中取出一颗或多颗石子。
  • 当一名玩家无法进行操作时,他输了,另一名玩家赢了。

当两个玩家玩得最佳时,这个游戏有两种可能:先移动的玩家总是获胜,或者第二移动的玩家总是获胜,仅取决于每堆石子的初始数量。

在这种情况下,第二个行动的高桥试图通过至少移动零和最多移动来保证他的胜利 (A_1 - 1) 石头来自 1-st 桩到 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

没有移动石子,如果青木先移走 2 石头来自 1-st一堆,高桥无论如何都赢不了。

如果高桥移动 1 石头来自 1-st 桩到 2- 在游戏开始之前,使两堆都有 4 石头,高桥只要正确选择他的行动,总能获胜。


示例输入 2

2
3 5

示例输出 2

-1

不允许从棋盘上移动棋子。 2-nd 堆到 1-st。


示例输入 3

3
1 1 2

示例输出 3

-1

不允许移动所有棋子 1-st 桩。


示例输入 4

8
10 9 8 7 6 5 4 3

示例输出 4

3

示例输入 5

3
4294967297 8589934593 12884901890

示例输出 5

1

注意溢出。