F. Вика и вики
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На днях Вика изучала свой любимый интернет-ресурс — Википедию.

На просторах Википедии она вычитала про интересную математическую операцию побитового исключающего ИЛИ, обозначаемую $$$\oplus$$$.

Вика стала изучать свойства этой загадочной операции. Для этого она взяла массив $$$a$$$, состоящий из $$$n$$$ целых неотрицательных чисел и применила одновременно ко всем его элементам следующую операцию: $$$a_i = a_i \oplus a_{(i+1) \bmod n}$$$. Здесь $$$x \bmod y$$$ обозначает остаток от деления $$$x$$$ на $$$y$$$. Элементы массива нумеруются, начиная с $$$0$$$.

Так как для полного изучения недостаточно проделать вышеописанные действия единожды, Вика повторяет их до тех пор, пока массив $$$a$$$ не превратится в состоящий только из нулей.

Определите, через сколько описанных выше действий все элементы массива $$$a$$$ станут нулевыми. Если такой момент никогда не наступит, выведите $$$-1$$$.

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

В первой строке находится единственное целое число $$$n$$$ ($$$1 \le n \le 2^{20}$$$) — длина массива $$$a$$$.

Гарантируется, что $$$n$$$ представимо в виде $$$2^k$$$ для некоторого целого числа $$$k$$$ ($$$0 \le k \le 20$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_0, a_1, a_2, \dots, a_{n-1}$$$ ($$$0 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

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

Выведите единственное число — минимальное число действий, необходимое, чтобы сделать все элементы массива $$$a$$$ нулевыми, или $$$-1$$$, если массив $$$a$$$ никогда не станет нулевым.

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

В первом примере после одной операции массив $$$a$$$ станет равен $$$[3, 3, 3, 3]$$$. Через ещё одну операцию он будет равен $$$[0, 0, 0, 0]$$$.

Во втором примере массив $$$a$$$ изначально состоит только из нулей.

В третьем примере после одной операции массив $$$a$$$ станет равен $$$[0]$$$.