У Васи есть последовательность \(a\) состоящая из \(n\) целых чисел \(a_1, a_2, \dots, a_n\). За одну операцию Вася может выбрать число из последовательности и поменять местами два любых бита в его двоичной записи. Например из числа \(6\) \((\dots 00000000110_2)\) Вася может получить числа \(3\) \((\dots 00000000011_2)\), \(12\) \((\dots 000000001100_2)\), \(1026\) \((\dots 10000000010_2)\) и так далее. Вася может применять эту операцию любое количество раз (возможно, ни разу) к любому из заданных чисел.
Вася считает последовательность чисел хорошей, если, применяя к ней описанную выше операцию, он может получить последовательность, побитовое исключающее ИЛИ всех элементов которой равно \(0\).
Для заданной последовательности \(a_1, a_2, \ldots, a_n\) Вася хочет знать количество пар целых чисел \((l, r)\) таких, что \(1 \le l \le r \le n\) и последовательность \(a_l, a_{l + 1}, \dots, a_r\) является хорошей.
Выходные данные
В единственной строке выведите одно целое число — количество пар целых чисел \((l, r)\) таких, что \(1 \le l \le r \le n\) и последовательность \(a_l, a_{l + 1}, \dots, a_r\) является хорошей.
Примечание
В первом примере подходят пары \((2, 3)\) и \((1, 3)\). Для пары \((2, 3)\) числа можно изменить следующим образом: \(a_2 = 7 \rightarrow 11\), \(a_3 = 14 \rightarrow 11\) и \(11 \oplus 11 = 0\), где \(\oplus\) — операция побитового исключающего ИЛИ. Для пары \((1, 3)\) числа можно изменить следующим образом: \(a_1 = 6 \rightarrow 3\), \(a_2 = 7 \rightarrow 13\), \(a_3 = 14 \rightarrow 14\) and \(3 \oplus 13 \oplus 14 = 0\).
Во втором примере подходят четыре пары: \((1, 2)\), \((2, 3)\), \((3, 4)\) и \((1, 4)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 7 14
|
2
|
|
2
|
4
1 2 1 16
|
4
|