F. Интересные отрезки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Василия есть массив неотрицательных чисел $$$a_1, a_2, \dots, a_n$$$. Он хочет, чтобы вы помогли ему узнать количество отрезков $$$l \le r$$$, которые проходят проверку. Проверка отрезка выполняется следующим образом:

  1. Находится минимум и максимум среди чисел на отрезке массива от $$$l$$$ до $$$r$$$.
  2. Проверка считается пройденной, если в битовой записи минимума и максимума одинаковое количество единичных бит.
Входные данные

Первая строка содержит одно число $$$n$$$ ($$$1 \le n \le 10^6$$$) — размер массива $$$a$$$.

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

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

Выведите одно число — количество отрезков, прошедших проверку.

Примеры
Входные данные
5
1 2 3 4 5
Выходные данные
9
Входные данные
10
0 5 7 3 9 10 1 6 13 7
Выходные данные
18