← 返回题目列表

AtCoder · arc168_b

B. 任意尼姆

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

分数: 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.