题目描述

小 X 拥有一个非递减（非递减是指一个数列中的元素从左到右依次不减）数组 $a_1, a_2, \dots, a_n$。

小 Y 因为它的美丽而感到嫉妒，想要破坏它的这个性质。他决定采用这样的方式去破坏： 每一步，选择数组中的两个相邻元素（设为 $x$ 和 $y$），将它们从数组中移除，并在它们的位置插入整数 $x \oplus y$，其中 $\oplus$ 表示按位异或运算。

例如，如果数组为 $[1, 2, 3]$，你可以选择 $1$ 和 $2$，用 $1 \oplus 2 = 3$ 替换它们。此时数组变为 $[3, 3]$。

小 Y 希望数组不再是非递减的。请问最少需要多少步？

输入格式

第一行包含一个整数 $n$，表示数组的初始长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组中的元素。

输出格式

输出一行一个整数，表示所需的最少操作次数。如果无论如何操作数组都始终保持非递减，输出 -1。

样例输入 1

4
2 5 6 8

样例输出 1

1

样例输入 2

3
1 2 3

样例输出 2

-1

样例输入 3

5
1 2 4 6 20

样例输出 3

2

说明

其它样例说明

• 样例 4：见选手目录下的 sequence/sequence4.in 与 sequence/sequence4.ans，该测试用例满足测试点 $1 \sim 4$ 的约束条件。
• 样例 5：见选手目录下的 sequence/sequence5.in 与 sequence/sequence5.ans，该测试用例满足测试点 $5 \sim 10$ 的约束条件。
• 样例 6：见选手目录下的 sequence/sequence6.in 与 sequence/sequence6.ans，该测试用例满足测试点 $11 \sim 14$ 的约束条件。

数据范围

• $2 \le n \le 10^5$
• $1 \le a_i \le 10^9$
• 保证对于所有的 $1 \le i < n$，都有 $a_i < a_{i+1}$（即原数组严格递增）。

各测试点的附加限制如下表所示：

点击下载大样例