К сожалению, английское название настолько хорошо, что не поддается успешному переводу на этот громоздкий язык.
Задан массив \(a_1, a_2, \dots, a_n\), состоящий из целых чисел.
Ваша задача — разделить его на максимальное количество подотрезков таким образом, чтобы:
- каждый элемент принадлежал ровно одному подотрезку;
- каждый подотрезок содержал хотя бы один элемент;
- не существовало непустого набора подотрезков такого, что побитовое исключающее ИЛИ чисел из них равнялось \(0\).
Выведите максимальное количество подотрезков, на которые можно разделить массив. Выведите -1, если не существует подходящего разделения.
Выходные данные
Выведите максимальное количество подотрезков, на которые можно разделить массив, соблюдая заданные правила. Выведите -1, если не существует подходящего разделения.
Примечание
В первом примере \(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\).