分数: 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
注意溢出。