Arkady 拥有一个非递减数组 $$$a_1, a_2, \ldots, a_n$$$。你嫉妒它的美丽并想毁掉它。您有一把所谓的“异或枪”,可以使用一次或多次。
在一步中,您可以选择数组中的两个连续元素,例如 $$$x$$$ 和 $$$y$$$,将它们从数组中删除并在其位置插入整数 $$$x \oplus y$$$,其中 $$$\oplus$$$ 表示按位异或运算。请注意,操作后数组的长度减一。当数组长度达到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
4 2 5 6 8
输出 #1
1
输入 #2
3 1 2 3
输出 #2
-1
输入 #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]$$$,不再是非递减的。