Solve in Python:
Vasya has a sequence $a$ consisting of $n$ integers $a_1, a_2, \dots, a_n$. Vasya may pefrom the following operation: choose some number from the sequence and swap any pair of bits in its binary representation. For example, Vasya can transform number $6$ $(\dots 00000000110_2)$ into $3$ $(\dots 00000000011_2)$, $12$ $(\dots 000000001100_2)$, $1026$ $(\dots 10000000010_2)$ and many others. Vasya can use this operation any (possibly zero) number of times on any number from the sequence.

Vasya names a sequence as good one, if, using operation mentioned above, he can obtain the sequence with bitwise exclusive or of all elements equal to $0$.

For the given sequence $a_1, a_2, \ldots, a_n$ Vasya'd like to calculate number of integer pairs $(l, r)$ such that $1 \le l \le r \le n$ and sequence $a_l, a_{l + 1}, \dots, a_r$ is good.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$) — length of the sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{18}$) — the sequence $a$.


-----Output-----

Print one integer — the number of pairs $(l, r)$ such that $1 \le l \le r \le n$ and the sequence $a_l, a_{l + 1}, \dots, a_r$ is good.


-----Examples-----
Input
3
6 7 14

Output
2

Input
4
1 2 1 16

Output
4



-----Note-----

In the first example pairs $(2, 3)$ and $(1, 3)$ are valid. Pair $(2, 3)$ is valid since $a_2 = 7 \rightarrow 11$, $a_3 = 14 \rightarrow 11$ and $11 \oplus 11 = 0$, where $\oplus$ — bitwise exclusive or. Pair $(1, 3)$ is valid since $a_1 = 6 \rightarrow 3$, $a_2 = 7 \rightarrow 13$, $a_3 = 14 \rightarrow 14$ and $3 \oplus 13 \oplus 14 = 0$.

In the second example pairs $(1, 2)$, $(2, 3)$, $(3, 4)$ and $(1, 4)$ are valid.
#!/usr/bin/env python3
import sys

def rint():
    return list(map(int, sys.stdin.readline().split()))
#lines = stdin.readlines()

def get_num1(i):
    cnt = 0
    while i:
        if i%2:
            cnt +=1
        i //=2
    return cnt

n = int(input())

a = list(rint())

b = [get_num1(aa) for aa in a]

ans = 0
#S0[i] : 1 if sum of 1s in ragne (0, i) is odd, else 0
S0 = [0]*n
S0[0] = b[0]%2
for i in range(1, n):
    S0[i] = (S0[i-1] + b[i])%2

#total even pairs in (0, n)
even_cnt = S0.count(0)

ans = even_cnt

# check total even pairs in (i, n)
for i in range(1, n):
    if b[i-1] %2:
        even_cnt = n - i - even_cnt
    else:
        even_cnt -= 1
    ans += even_cnt

for i in range(n):
    max_value = 0
    sum_value = 0
    for j in range(1, 62):
        if i + j > n:
            break
        sum_value += b[i+j-1]
        max_value = max(max_value, b[i+j-1])
        if 2 * max_value > sum_value and sum_value%2 == 0:
            ans -= 1

print(ans)