На перемене Ваня зашел в класс и увидел на доске массив из \(n\) целых неотрицательных \(k\)-битных чисел \(a_1, a_2, \ldots, a_n\). Число \(x\) называется \(k\)-битным, если \(0 \leq x \leq 2^k - 1\).
Естественно, Ваня не удержался и стал менять числа, написанные на доске. Для того, чтобы никто ничего не заметил, Ваня разрешил себе сделать несколько следующих изменений: выбрать индекс массива \(i\) (\(1 \leq i \leq n\)) и заменить число \(a_i\) на число \(\overline{a_i}\). Будем обозначать за \(\overline{x}\) для \(k\)-битного числа \(x\) такое \(k\)-битное число, что все его \(k\) битов отличаются от соответствующих битов числа \(x\).
Ване очень не нравится число \(0\). Поэтому ему нравятся такие отрезки \([l, r]\) (\(1 \leq l \leq r \leq n\)), что \(a_l \oplus a_{l+1} \oplus \ldots \oplus a_r \neq 0\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ. Определите, какое максимальное количество таких отрезков он сможет получить, выполнив несколько (возможно, ноль) операций, описанных выше.
Выходные данные
Выведите одно целое число — максимальное возможное количество отрезков с побитовым исключающим ИЛИ, не равным \(0\), которое можно получить, сделав несколько (возможно, \(0\)) операций, описанных в условии.
Примечание
В первом тесте можно не делать операций, тогда мы получим, что у нас \(5\) отрезков, которые нравятся Ване. Если сделать операцию с \(i = 2\), то получится массив \([1, 0, 0]\), так как \(\overline{3} = 0\) при \(k = 2\). У такого массива будет \(3\) подотрезка, которые нравятся Ване. Можно получить массив с \(5\) подотрезками, которые нравятся Ване, если сделать операцию с \(i = 3\) и операцию с \(i = 2\). Тогда получится массив \([1, 0, 3]\). Можно доказать, что \(6\) и более отрезков, которые будут нравиться Ване, получить невозможно.
Во втором тесте, чтобы получить \(19\) подотрезков, которые нравятся Ване, можно сделать \(4\) операции с \(i = 3\), \(i = 4\), \(i = 5\) и \(i = 6\). Получится массив \([1, 4, 3, 0, 4, 3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 3 0
|
5
|
|
2
|
6 3
1 4 4 7 3 4
|
19
|