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

У Васи есть последовательность $$$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$$$ является хорошей.

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — длину последовательности.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — саму последовательность $$$a$$$.

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

В единственной строке выведите одно целое число — количество пар целых чисел $$$(l, r)$$$ таких, что $$$1 \le l \le r \le n$$$ и последовательность $$$a_l, a_{l + 1}, \dots, a_r$$$ является хорошей.

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

В первом примере подходят пары $$$(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)$$$.