不公平的尼姆

题目描述

有 $N$ 堆石子,第 $i$ 堆有 $A_i$ 个石子。

青木君和高桥君打算用它玩下面这样的游戏:

• 青木君先手,两人交替重复以下操作

• 操作:选择 $1$ 堆石子,从中取走 $1$ 个以上的石子

• 先无法进行操作的一方输

在两人都采取最优策略的情况下,这个游戏的胜负仅由游戏开始时各堆石子的个数决定,先手必胜或后手必胜。

于是,高桥君打算在游戏开始前,从第 $1$ 堆取走 $0$ 个以上、少于 $A_1$ 个的石子移到第 $2$ 堆,使得后手的高桥君必胜。

如果这样做是可能的,输出移动的石子个数的最小值;如果不可能,则输出 -1。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $\ldots$ $A_N$

输出格式

输出移动的石子个数的最小值。如果不可能,则输出 -1。

样例

2
5 3

1

如果不移动石子,青木君先手从第 $1$ 堆取走 $2$ 个石子后,无论高桥君之后如何行动都会输。

如果在游戏开始前从第 $1$ 堆移动 $1$ 个石子,使石子个数变为 $4,4$,那么通过恰当的行动,高桥君必胜。

2
3 5

-1

无法把石子从第 $2$ 堆移到第 $1$ 堆。

3
1 1 2

-1

不能移动第 $1$ 堆的所有石子。

8
10 9 8 7 6 5 4 3

3

3
4294967297 8589934593 12884901890

1

请注意溢出。

数据范围

• $2 \leq N \leq 300$
• $1 \leq A_i \leq 10^{12}$