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.

Difficulty: interview

Starter code:

Solutions:
#!/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)


n = int(input())

cnt = [[0 for _ in range(n + 1)] for _ in range(2)]

b = [bin(_).count('1') for _ in list(map(int, input().split()))]

res = 0

suf_sum = 0

cnt[0][n] = 1

for i in range(n)[::-1]:
	_sum, mx = 0, 0
	lst_j = i
	add = 0

	for j in range(i, min(n, i + 65)):
		_sum += b[j]

		mx = max(mx, b[j])

		if mx > _sum - mx and _sum % 2 == 0:
			add -= 1
		
		lst_j = j
		
	suf_sum += b[i]
	add += cnt[suf_sum & 1][i + 1]
	res += add
	
	cnt[0][i] = cnt[0][i + 1]
	cnt[1][i] = cnt[1][i + 1]
	
	if suf_sum & 1:
		cnt[1][i] += 1
	else:
		cnt[0][i] += 1
	
print(res)


from array import array
def popcount(x):
    res = 0;
    while(x > 0):
        res += (x & 1)
        x >>= 1
    return res

def main():
    n = int(input())
    a = array('i',[popcount(int(x)) for x in input().split(' ')])

    ans,s0,s1 = 0,0,0
    for i in range(n):
        if(a[i] & 1):
            s0,s1 = s1,s0 + 1
        else:
            s0,s1 = s0 + 1, s1
        ans += s0

    for i in range(n):
        mx,sum = a[i],0
        for j in range(i, min(n, i + 70)):
            mx = max(mx, a[j]<<1)
            sum += a[j]
            if( (sum & 1 is 0) and (mx > sum)):
                ans-=1
    print(ans)
main()



n = int(input())

a= list(map(int,input().split()))


for i in range(n):
    x = bin(a[i])
    a[i] = x.count('1')
    

even = 0
odd = 0
cnt = 0
#print(a)
sofar = 0
for i in range(n):
    sofar += a[i]
    if(sofar % 2):
        odd += 1
    else:
        even += 1
even += 1
#print(even,odd)       
sofar = 0
for i in range(n):
    if(sofar % 2):
        odd -= 1
        cnt += odd
    else:
        even -= 1
        cnt += even
    sofar += a[i]

#print(cnt)
for i in range(n):
    sum1 = 0
    max1 = a[i]
    for j in range(i, min(i + 100 , n) ):
        sum1 += a[j]
        max1 = max(max1,a[j])
        if(sum1 % 2 == 0 and sum1 < 2*max1):
            cnt -= 1
print(cnt)
    


N = int(input())
a = list(map(int, input().split()))
cnt = [[0] * (N + 1) for i in range(2)]
b = [0] * N
for i in range(N):
    b[i] = bin(a[i]).count("1")
num = 0
suf = 0
cnt[0][N] = 1
for i in range(N - 1, -1, -1):
    s = 0
    ma = 0
    add = 0
    for j in range(i, min(N, i + 65)):
        s += b[j]
        ma = max(ma, b[j])
        if ma * 2 > s and s % 2 == 0:
            add -= 1

    suf += b[i]
    add += cnt[suf & 1][i + 1]
    num += add

    cnt[0][i] = cnt[0][i + 1]
    cnt[1][i] = cnt[1][i + 1]
    if suf & 1:
        cnt[1][i] += 1
    else:
        cnt[0][i] += 1

print(num)

N = int(input())
a = list(map(int, input().split()))
cnt = [[0] * (N + 1) for i in range(2)]
b = [0] * N
for i in range(N):
    b[i] = bin(a[i]).count("1")
num = 0
suf = 0
cnt[0][N] = 1
for i in range(N - 1, -1, -1):
    s = 0
    ma = 0

    suf += b[i]
    num += cnt[suf & 1][i + 1]

    for j in range(i, min(N, i + 65)):
        s += b[j]
        ma = max(ma, b[j])
        if ma * 2 > s and s % 2 == 0:
            num -= 1

    cnt[0][i] = cnt[0][i + 1]
    cnt[1][i] = cnt[1][i + 1]
    if suf & 1:
        cnt[1][i] += 1
    else:
        cnt[0][i] += 1

print(num)