分数: 400 点
问题陈述
有 N 成堆的石头,以及 i- 第堆 (1 \leq i \leq N)有 A_i 石头。
您将选择一个正整数 k。 然后,爱丽丝和鲍勃将用这些桩玩一个游戏,如下所示。
- 从Alice开始,玩家轮流玩。
- 在每个回合中,玩家必须选择一个非空堆并从中移走一定数量的石子 1 和 k,包括在内。
轮到自己不能移动的人就输了,另一个人就赢了。
您想要选择一个正整数 k 爱丽丝有一个获胜策略。 确定是否有这样一个 k 存在。 如果存在,判断是否存在最大值 k。 如果存在最大值,请提供该值。
约束
- 1 \leq N \leq 250000
- 1 \leq A_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
如果没有 k Alice 有获胜策略,打印 0.
如果有 k Alice 有一个获胜策略,并且这种策略没有最大值 k,打印 -1.
如果有 k 爱丽丝有一个获胜策略,并且这种策略有一个最大值 k,打印该值。
示例输入 1
3 1 2 3
示例输出 1
2
例如,如果 k=2,爱丽丝有一个获胜策略。 如果 k \geq 3,Alice没有获胜策略,所以答案是 k=2.
示例输入 2
4 1 2 3 4
示例输出 2
-1
例如,爱丽丝对所有的人都有获胜策略 k=100,200,300,\cdots。 因此,没有最大值 k,所以打印 -1.
示例输入 3
2 100 100
示例输出 3
0
无论如何 选择 k ,Alice 没有获胜策略。 因此,打印 0.