Vasya has a sequence 𝑎a consisting of 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an. 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 66 (…000000001102)(…000000001102) into 33 (…000000000112)(…000000000112), 1212 (…0000000011002)(…0000000011002), 10261026 (…100000000102)(…100000000102) 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 00.

For the given sequence 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an Vasya'd like to calculate number of integer pairs (𝑙,𝑟)(l,r) such that 1≤𝑙≤𝑟≤𝑛1≤l≤r≤n and sequence 𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟al,al+1,…,ar is good.

Input

The first line contains a single integer 𝑛n (1≤𝑛≤3⋅1051≤n≤3⋅105) — length of the sequence.

The second line contains 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤10181≤ai≤1018) — the sequence 𝑎a.

Output

Print one integer — the number of pairs (𝑙,𝑟)(l,r) such that 1≤𝑙≤𝑟≤𝑛1≤l≤r≤n and the sequence 𝑎𝑙,𝑎𝑙+1,…,𝑎𝑟al,al+1,…,ar is good.

Note

In the first example pairs (2,3)(2,3) and (1,3)(1,3) are valid. Pair (2,3)(2,3) is valid since 𝑎2=7→11a2=7→11, 𝑎3=14→11a3=14→11 and 11⊕11=011⊕11=0, where ⊕⊕ — bitwise exclusive or. Pair (1,3)(1,3) is valid since 𝑎1=6→3a1=6→3, 𝑎2=7→13a2=7→13, 𝑎3=14→14a3=14→14 and 3⊕13⊕14=03⊕13⊕14=0.

In the second example pairs (1,2)(1,2), (2,3)(2,3), (3,4)(3,4) and (1,4)(1,4) are valid.