D. XOR-пушка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Аркадия есть неубывающий массив натуральных чисел $$$a_1, a_2, \ldots, a_n$$$. Вы завидуете ему и хотите уничтожить это свойство. У вас есть так называемая XOR-пушка, которую вы можете использовать один или несколько раз.

За один шаг вы можете выбрать два последовательных элемента в массиве, обозначим их за $$$x$$$ и $$$y$$$, удалить их из массива и на их место вставить число $$$x \oplus y$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ. Обратите внимание, что длина массива уменьшается на один в результате этой операции. Вы не можете выполнить эту операцию, если длина массива стала единицей.

Например, если массив равен $$$[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$$$) — элементы массива. Гарантируется, что $$$a_i \le a_{i + 1}$$$ для всех $$$1 \le i < n$$$.

Выходные данные

Выведите одно целое число — минимальное необходимое число шагов. Если решения не существует, выведите $$$-1$$$.

Примеры
Входные данные
4
2 5 6 8
Выходные данные
1
Входные данные
3
1 2 3
Выходные данные
-1
Входные данные
5
1 2 4 6 20
Выходные данные
2
Примечание

В первом примере можно выбрать $$$2$$$ и $$$5$$$, и массив станет равным $$$[7, 6, 8]$$$.

Во втором примере можно получить только массивы $$$[1, 1]$$$, $$$[3, 3]$$$ и $$$[0]$$$, которые все являются неубывающими.

В третьем примере можно выбрать $$$1$$$ и $$$2$$$ и массив станет равным $$$[3, 4, 6, 20]$$$. Затем вы можете, например, выбрать $$$3$$$ и $$$4$$$ и массив станет равным $$$[7, 6, 20]$$$. Этот массив не является неубывающим.