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

К сожалению, английское название настолько хорошо, что не поддается успешному переводу на этот громоздкий язык.

Задан массив $$$a_1, a_2, \dots, a_n$$$, состоящий из целых чисел.

Ваша задача — разделить его на максимальное количество подотрезков таким образом, чтобы:

  • каждый элемент принадлежал ровно одному подотрезку;
  • каждый подотрезок содержал хотя бы один элемент;
  • не существовало непустого набора подотрезков такого, что побитовое исключающее ИЛИ чисел из них равнялось $$$0$$$.

Выведите максимальное количество подотрезков, на которые можно разделить массив. Выведите -1, если не существует подходящего разделения.

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

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — размер массива.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

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

Выведите максимальное количество подотрезков, на которые можно разделить массив, соблюдая заданные правила. Выведите -1, если не существует подходящего разделения.

Примеры
Входные данные
4
5 5 7 2
Выходные данные
2
Входные данные
3
1 2 3
Выходные данные
-1
Входные данные
3
3 1 10
Выходные данные
3
Примечание

В первом примере $$$2$$$ — максимальный ответ. Если разделить массив на $$$\{[5], [5, 7, 2]\}$$$, то значения исключающего ИЛИ набора только из второго подотрезка будет $$$5 \oplus 7 \oplus 2 = 0$$$. У $$$\{[5, 5], [7, 2]\}$$$ значение исключающего ИЛИ набора только из первого подотрезка будет $$$5 \oplus 5 = 0$$$. Однако, разделение $$$\{[5, 5, 7], [2]\}$$$ приведет к наборам $$$\{[5, 5, 7]\}$$$ со значением $$$7$$$, $$$\{[2]\}$$$ — со значением $$$2$$$ и $$$\{[5, 5, 7], [2]\}$$$ — со значением $$$5 \oplus 5 \oplus 7 \oplus 2 = 5$$$.

Взглянем на какое-нибудь разделение из $$$3$$$ отрезков — $$$\{[5], [5, 7], [2]\}$$$. Оно образует следующие наборы:

  • $$$\{[5]\}$$$, XOR $$$5$$$;
  • $$$\{[5, 7]\}$$$, XOR $$$2$$$;
  • $$$\{[5], [5, 7]\}$$$, XOR $$$7$$$;
  • $$$\{[2]\}$$$, XOR $$$2$$$;
  • $$$\{[5], [2]\}$$$, XOR $$$7$$$;
  • $$$\{[5, 7], [2]\}$$$, XOR $$$0$$$;
  • $$$\{[5], [5, 7], [2]\}$$$, XOR $$$5$$$;

Как можно заметить, набор $$$\{[5, 7], [2]\}$$$ имеет значение $$$0$$$, что неприемлемо. Можете проверить, что и другие разделения размера $$$3$$$ или $$$4$$$ имеют хотя бы один набор со значением $$$0$$$.

Во втором примере не существует подходящего разделения.

В третьем примере массив может быть разделен на $$$\{[3], [1], [10]\}$$$. Ни один набор из подотрезков этого разделения имеет значение $$$0$$$.