题目描述

Arkady 拥有一个非递减数组 $a_1, a_2, \ldots, a_n$。你因为它的美丽而感到嫉妒，想要破坏它的这个性质。你有一把所谓的 XOR-枪，可以使用一次或多次。

每一步，你可以选择数组中两个相邻的元素，记为 $x$ 和 $y$，将它们从数组中移除，并在它们的位置插入整数 $x \oplus y$，其中 $\oplus$ 表示按位异或运算。注意，每次操作后数组长度减少 $1$。当数组长度为 $1$ 时，不能再进行此操作。

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

你希望数组不再是非递减的。请问最少需要多少步？如果无论如何操作数组都始终保持非递减，请输出 $-1$。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示数组的初始长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示数组的元素。保证对于所有 $1 \le i < n$，都有 $a_i \le a_{i+1}$。

输出格式

输出一个整数，表示所需的最小操作次数。如果无解，输出 $-1$。

输入输出样例 #1

输入 #1

4
2 5 6 8

输出 #1

1

输入输出样例 #2

输入 #2

3
1 2 3

输出 #2

-1

输入输出样例 #3

输入 #3

5
1 2 4 6 20

输出 #3

2

说明/提示

在第一个样例中，你可以选择 $2$ 和 $5$，数组变为 $[7, 6, 8]$。

在第二个样例中，你只能得到 $[1, 1]$、$[3, 3]$ 和 $[0]$，它们都是非递减的。

在第三个样例中，你可以选择 $1$ 和 $2$，数组变为 $[3, 4, 6, 20]$。然后你可以选择 $3$ 和 $4$，数组变为 $[7, 6, 20]$，此时数组不再是非递减的。