题目描述

有 $N$ 堆石子，第 $i$ 堆（$1 \leq i \leq N$）有 $A_i$ 个石子。

你现在可以选择一个正整数 $k$。之后，Alice 和 Bob 会用这些石子堆进行如下游戏：

• 游戏由 Alice 先手，双方轮流进行操作。
• 每一回合，当前玩家选择一个非空的石子堆，从中取走任意数量的石子，数量不少于 $1$ 个且不多于 $k$ 个。

无法进行操作的一方判负，未被判负的一方获胜。

你需要选择一个正整数 $k$，使得 Alice 存在必胜策略。请判断是否存在这样的 $k$。如果存在，判断是否存在使 Alice 必胜的 $k$ 的最大值。如果最大值存在，请输出该最大值。

输入格式

输入以如下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

如果不存在使 Alice 必胜的 $k$，输出 $0$。

如果存在使 Alice 必胜的 $k$，但不存在最大值，输出 $-1$。

如果存在使 Alice 必胜的 $k$，且最大值存在，输出该最大值。

样例 1

输入

3
1 2 3

输出

2

样例 2

输入

4
1 2 3 4

输出

-1

样例 3

输入

2
100 100

输出

0

说明/提示

限制条件

• $1 \leq N \leq 250000$
• $1 \leq A_i \leq 10^9$
• 输入的所有值均为整数。

样例解释 1

例如，当 $k=2$ 时，Alice 存在必胜策略。若选择 $k \geq 3$，Alice 就没有必胜策略，因此答案为 $k=2$。

样例解释 2

例如，对于所有 $k=100,200,300,\cdots$，Alice 都存在必胜策略。因此不存在最大值，输出 $-1$。

样例解释 3

无论选择怎样的 $k$，Alice 都没有必胜策略。因此输出 $0$。

由 ChatGPT 4.1 翻译