У Василия есть массив неотрицательных чисел \(a_1, a_2, \dots, a_n\). Он хочет, чтобы вы помогли ему узнать количество отрезков \(l \le r\), которые проходят проверку. Проверка отрезка выполняется следующим образом:
- Находится минимум и максимум среди чисел на отрезке массива от \(l\) до \(r\).
- Проверка считается пройденной, если в битовой записи минимума и максимума одинаковое количество единичных бит.
Выходные данные
Выведите одно число — количество отрезков, прошедших проверку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 3 4 5
|
9
|
|
2
|
10
0 5 7 3 9 10 1 6 13 7
|
18
|