У Аркадия есть неубывающий массив натуральных чисел \(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\).
Выходные данные
Выведите одно целое число — минимальное необходимое число шагов. Если решения не существует, выведите \(-1\).
Примечание
В первом примере можно выбрать \(2\) и \(5\), и массив станет равным \([7, 6, 8]\).
Во втором примере можно получить только массивы \([1, 1]\), \([3, 3]\) и \([0]\), которые все являются неубывающими.
В третьем примере можно выбрать \(1\) и \(2\) и массив станет равным \([3, 4, 6, 20]\). Затем вы можете, например, выбрать \(3\) и \(4\) и массив станет равным \([7, 6, 20]\). Этот массив не является неубывающим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 5 6 8
|
1
|
|
2
|
3
1 2 3
|
-1
|
|
3
|
5
1 2 4 6 20
|
2
|