该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题意】

游戏开始时有许多硬币任意分布在楼梯上，共 $n$ 阶楼梯从地面由下向上编号为 $0$ 到 $n$。

游戏者在每次操作时可以将楼梯 $i$（$1 \le i \le n$）上的任意多但至少一个硬币移动到楼梯 $i-1$ 上。

游戏者轮流操作，将最后一枚硬币移至地上的人获胜。

【输入格式】

多组数据。

第一行为整数 $n \ (1 \le n \le 10^6, \sum n \le 10^6)$。

第二行为 $n$ 个整数 $a_i \ (0 \le a_i \le 10^{15})$，$a_i$ 表示第 $i$ 阶楼梯的硬币数。

【输出格式】

每组数据输出一行 ，如果先手赢则输出第一步操作的方案数，否则输出 $0$。

【样例输入】

4
1 1 1 1
5
1 2 4 6 1
5
11 2 2 54 98

【样例输出】

0
1
1