题目描述

Gena 和 Petya 玩 Nim 游戏。桌上有 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子。两人轮流操作，Gena 先手。每次操作选择一个非空石子堆并从中拿走任意正数个石子；无法操作的人失败。

两人都会采用最优策略。

Petya 觉得 Gena 总是先手不公平，于是决定在游戏开始前偷偷从每一堆中拿走相同数量的石子。设拿走的数量为 $x$，要求：

$0\le x<\min_i a_i$。

拿走之后，第 $i$ 堆剩余 $a_i-x$ 个石子，然后由 Gena 先手开始正常 Nim 游戏。

求有多少个不同的整数 $x$ 能使 Petya 在双方最优策略下获胜。

输入格式

第一行一个整数 $n$，$1\le n\le2\times10^5$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，$1\le a_i\le10^{18}$。

输出格式

输出一个整数，表示满足条件的 $x$ 的数量。

样例 1

样例输入

2
3 3

样例输出

3

样例 2

样例输入

3
3 4 5

样例输出

1

样例 3

样例输入

4
2 7 4 1

样例输出

1

样例 4

样例输入

4
4 6 8 10

样例输出

2

样例说明

第一组样例中 $x=0,1,2$ 均可使两堆石子保持相等，因此 Petya 获胜。第二组样例唯一可行的 $x$ 为 $2$；第三组为 $0$；第四组为 $0$ 和 $3$。