Problem:
 Score : 500 points    Problem Statement There is an integer sequence A of length N .  Find the number of the pairs of integers l and r ( 1 \leq l \leq r \leq N ) that satisfy the following condition:   A_l\ xor\ A_{l+1}\ xor\ ...\ xor\ A_r = A_l\ +\ A_{l+1}\ +\ ...\ +\ A_r   Here, xor denotes the bitwise exclusive OR.   Definition of XOR  The XOR of integers c_1, c_2, ..., c_m is defined as follows:   Let the XOR be X . In the binary representation of X , the digit in the 2^k 's place ( 0 \leq k ; k is an integer) is 1 if there are an odd number of integers among c_1, c_2, ...c_m whose binary representation has 1 in the 2^k 's place, and 0 if that number is even.   For example, let us compute the XOR of 3 and 5 . The binary representation of 3 is 011 , and the binary representation of 5 is 101 , thus the XOR has the binary representation 110 , that is, the XOR is 6 .

Solution (Python):









import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    
    
    
    n= int(input())
    s = list(map(int,input().split()))
    
    r, ans, tmp = 0, 0, 0
    for l in range(n):
        
        while r < n and tmp ^ s[r]==tmp+s[r]:
            tmp ^= s[r]
            r += 1

        
        
        ans += r - l 

        
        if l == r:  
            r += 1
        else:
            
            
            tmp ^= s[l]
            
        
        
    print(ans)
    
    
resolve()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
ans=0

l=r=s=0
while l<n:
    if s^a[r]==s+a[r]:
        s+=a[r]
        if r!=n-1:
            r+=1
        else:
            break
    else:
        ans+=r-l
        s-=a[l]
        l+=1

ans+=(r-l+1)*(r-l+2)//2

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

l = 0
now = 0
ans = 0
for i in range(N):
    var = As[i]
    if now+var==now^var:
        ans += (i-l+1)
        now += var
    else:
        while l<=i:
            lvar = As[l]
            l += 1
            now -= lvar
            if now+var==now^var:
                now += var
                ans += (i-l+1)
                break
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int,readline().split()))




right = 0
xor = 0 
ans = 0

def isOk(x, v):

  K = min(x, v)
  while K:
    if (x & 1) and (v & 1):

      return False
    K >>= 1
    x >>= 1
    v >>= 1

  return True

for left in range(N):
  while right < N:
    if isOk(xor, A[right]): 
      xor ^= A[right]
      right += 1
    else:
      break
      

  ans += (right - left)
  

  
  if right == left:
    right += 1
  else:
    xor ^= A[left]
  
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
clashes=[-1]*20
ans=0
lastclash=-1
for i in range(n):
  binstr='{0:b}'.format(a[i])
  binlist=[]
  t=len(binstr)
  for j in range(t):
    binlist.append(binstr[j])
  binlist.reverse()
  for j in range(20-t):
    binlist.append('0')
  maxclash=-1
  for j in range(20):
    if clashes[j]>maxclash and binlist[j]=='1':
      maxclash=clashes[j]
  for j in range(20):
    if binlist[j]=='1':
      clashes[j]=i
  lastclash=max(maxclash,lastclash)
  ans+=i-lastclash
print(ans)

Solution (Python):
import math



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            

def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))










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

left=0
right=0
total = a[0]
xor = a[0]
ans=1
while(True):
    if(right == n-1):
        break
    
    right+=1
    xor ^= a[right]
    total += a[right]
    while(total!=xor):
        xor ^= a[left]
        total -= a[left]
        left+=1
    ans += right - left + 1

print(ans)

Solution (Python):
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

N = I()
A = [0] + LI()

from itertools import accumulate

B = [[0]*(N+1) for _ in range(20)]
for i in range(20):
    for j in range(N+1):
        B[i][j] = (A[j] >> i) & 1
for i in range(20):
    B[i] = list(accumulate(B[i]))




ans = 0
left = 0
right = 1

while right < N+1:
    for i in range(20):
        if B[i][right] - B[i][left] <= 1:
            continue
        else:
            ans += right - left - 1
            left += 1
            break
    else:
        right += 1

ans += ((right - left)*(right - left - 1))//2

print(ans)

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]

S = 0
r = 0
ans = 0
for l, a in enumerate(A):
	while r < N and S + A[r] == S ^ A[r]:
		S += A[r]
		r += 1
	ans += r - l	
	S -= a
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

cnt, su, r = 0, 0, 0
for l in range(n):
    while r < n and su + a[r] == su ^ a[r]:
        su += a[r]
        r += 1
    cnt += r - l
    if l == r:
        r += 1
    else:
        su -= a[l]
print(cnt)

Solution (Python):
def main():
    from collections import deque

    N = int(input())
    A = map(int, input().split())

    ans = 0
    dq = deque()
    xor_ = 0
    for x in A:
        while xor_ & x:  
            xor_ ^= dq.popleft()
        xor_ ^= x
        dq.append(x)
        ans += len(dq)  
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
cnt=0
r=0
ga=g=a[0]
xa=x=a[0]
for l in range(n):
    while r<n-1:
        g=ga+a[r+1]
        x=xa|a[r+1]
        if g==x:
            ga=g
            xa=x
            r+=1
        else:
            break
        if r==n-1:
            break
    cnt+=r-l+1
    ga-=a[l]
    xa-=a[l]
print(cnt)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))

total = 0
ans = 0
r = 0

for l in range(n):
    while r < n and total+a[r] == total^a[r]:
        total += a[r]
        r += 1
    ans += r-l
    if l == r:
        r += 1
    else:
        total -= a[l]

print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

left=0;right=0
SUM = 0
ans = 0
for left in range(N):
  while right < N and  SUM+A[right] == SUM^A[right]:
    SUM += A[right]
    right += 1
    
  ans += right-left
  
  if right == left:
    right += 1
    
  else:
    SUM -= A[left]
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

left=0;right=0
SUM = 0
ans = 0
for i in range(N):
  left = i
  while right < N and  SUM+A[right] == SUM^A[right]:
    SUM += A[right]
    right += 1
    
  ans += right-left
  
  if right == left:
    right += 1
    
  else:
    SUM -= A[left]
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
accu = [0]*20
ans = 0
r = 0
for l in range(n):
    while r<n:
        tmp = accu[:]
        for i in range(20):
            tmp[i] += a[r]>>i&1
        if max(tmp)==2:
            break
        accu = tmp
        r += 1
    ans += r-l
    for i in range(20):
        accu[i] -= a[l]>>i&1
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))

bitruiseki = [[0]*21 for i in range(n+1)]

for i in range(n):
    ref = a[i]
    for j in range(20,-1,-1):
        if ref >= (1 << j):
            bitruiseki[i+1][j] = bitruiseki[i][j] + 1
            ref %= (1 << j)
        else:
            bitruiseki[i+1][j] = bitruiseki[i][j]

def check(l,r):
    for i in range(21):
        if bitruiseki[r][i] - bitruiseki[l][i] <= 1:
            pass
        else:
            return False
    return True


ans = 0
right = 1
for i in range(n+1):
    right = max(right,i)
    if right < n:
        while (check(i,right+1) and right < n):
            right += 1
            if right == n:break
    ans += right - i
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

ru_xor = [0] * (n + 1)
ru_sum = [0] * (n + 1)

for i in range(n):
    ru_xor[i + 1] = ru_xor[i] ^ a[i]
    ru_sum[i + 1] = ru_sum[i] + a[i]

r = 0
ans = 0
for l in range(n):
    while not(r == n + 1) and ru_xor[r] ^ ru_xor[l] == ru_sum[r] - ru_sum[l]:
        r += 1
    ans += (r - 1) - l
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

S = 0
r = 0
ans = 0
for l, a in enumerate(A):
    while r < N and S + A[r] == S ^ A[r]:
        S += A[r]
        r += 1
    ans += r - l
    S -= a
print(ans)

Solution (Python):
N = int(input())
L = list(map(int,input().split()))

bit =[[0 for i in range(20)] for _ in range(N+1)]
for j in range(N):
    for i in range(20):
        bit[j+1][i] = (L[j] >> i) & 1

for j in range(1,len(L)):
    for i in range(20):
        bit[j+1][i] += bit[j][i]



def check(start,x):
    
    for i in range(20):
        if bit[x][i] - bit[start][i] >= 2:
            return False
    return True


def bisect(start,x,y):
    if y - x == 1: return x
    mid = (x + y) // 2
    if check(start,mid) == False:
        return bisect(start,x,mid)
    else:
        return bisect(start,mid,y)

cnt = 0

for n in range(N):
    
    cnt += bisect(n, n, N+1) - n
print(cnt)

Solution (Python):
N = int(input())
L = list(map(int,input().split()))
cand = []
bit =[[0 for i in range(20)] for _ in range(N)]
for j in range(len(L)):
    for i in range(20):
        bit[j][i] = (L[j] >> i) & 1
for j in range(1,len(L)):
    for i in range(20):
        bit[j][i] += bit[j-1][i]
bit = [[0 for i in range(20)]] + bit



def check(start,x):
    for i in range(20):
        if bit[x][i] - bit[start][i] >= 2:
            return False
    return True


def bisect(start,x,y):
    if y - x == 1: return x
    mid = (x + y) // 2
    if check(start,mid) == False:
        return bisect(start,x,mid)
    else:
        return bisect(start,mid,y)

cnt = 0
for n in range(N):
    cnt += bisect(n, n, N+1) - n
 
print(cnt)

Solution (Python):
N=int(input())
A=list(map(int, input().split()))
left=0
a=0
cnt=0
for right in range(N):
  if a&A[right]:
    while a&A[right]:
      a^=A[left]
      left+=1
  cnt+=right-left
  a^=A[right]
print(cnt+N)

Solution (Python):
n = int(input())

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

left = 0
right = 1

cur_sum = a[0]
cur_xor = a[0]

ans = 0

while right <= n:
    if cur_sum == cur_xor:
        ans += right - left
        right += 1
        if right > n:
            break
        cur_sum += a[right-1]
        cur_xor ^= a[right-1]
    else:
        cur_sum -= a[left]
        cur_xor ^= a[left]
        left += 1

print(ans)

Solution (Python):



"""

配列Aに対し、区間l,rを決めて、Al~Arのxor取ったやつと、足したやつが一致すればいい

a xor b = a + b が成立するとき、aとbを２進数で見たときに、i番目のビットが両方1になっている、ということがない。


"""


N = int(input())
A = list(map(int, input().split()))

bits= [-1] * 21
r = 0

ans = 0
for l in range(N):
    while r <= N-1:
        flag = True
        for j in range(21):
            if bits[j] != -1 and A[r] & (1 << j):
                flag = False
                break

        if flag:
            for j in range(21):
                if A[r] & (1 << j):
                    bits[j] = r
            r += 1

        else:
            break


    ans += r - l

    if l == r:
        r += 1

    for j in range(21):
        if A[l] & (1 << j):
            bits[j] = -1

print(ans)

Solution (Python):
n=int(input())
A=[int(i) for i in input().split()]

ans=0
left=0
right=0
tas=A[0]
xor=A[0]

while right<n-1 and left<n:
    if tas+A[right+1] == xor^A[right+1]:
        right+=1
        ans+=right-left
        tas+=A[right]
        xor^=A[right]
    else:
        tas-=A[left]
        xor^=A[left]
        left+=1

print(ans+n)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

c = 0
l = 0
ans = 0

for r in range(N):
    a = A[r]
    if c&a:
        while c&a:
            c = c^A[l]
            l += 1
    c = c^a
    ans += r-l+1

print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

c = 0
l = 0
ans = 0

for r in range(N):
    if c&A[r]:
        while c&A[r]:
            c = c^A[l]
            l += 1
    c = c^A[r]
    ans += r-l+1

print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

c = 0
l = 0
ans = 0

for r,a in enumerate(A):
    if c&a:
        while c&a:
            c = c^A[l]
            l += 1
    c = c^a
    ans += r-l+1

print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))

c = [0 for j in range(20)]

l = 0

ans = 0

for r,a in enumerate(A):
    
    for j in range(20):
        c[j] += (a>>j)&1
    
    while sum(c[j] < 2 for j in range(20)) != 20:

        b = A[l]
        for j in range(20):
            c[j] -= (b>>j)&1
        l += 1
    
    ans += (r-l+1)

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return (int(x) for x in input().split())
def LI(): return list(Is())
def TI(): return tuple(Is())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(S())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18


n = I()
A = LI()

def r_increment(r, x, y):
    return r+1, x^A[r], y+A[r]  

def l_increment(l, x, y):
    return l+1, x^A[l], y-A[l]  

def check(x, y):
    return x == y

ans = 0
r = 0
x = 0
y = 0
for l in range(n):
    while r < n and check(x^A[r], y+A[r]):
        r, x, y = r_increment(r, x, y)

    
    
    if not l == r:
        ans += r-l

    if l < r:
        _, x, y = l_increment(l, x, y)
    else:
        _, x, y = l_increment(l, x, y)
        r, x, y = r_increment(r, x, y)

print(ans)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

def func(c, S):
    b = list(format(c, 'b'))
    b = list(reversed(b))
    flag = True
    for i in range(len(b)):
        if b[i] == '1' and S[i] == 1:
            flag = False
            break
    return flag

p = 0
q = 0
S = [0]*30
ans = 0
for p in range(n):
    while q < n and func(A[q], S):
        b = list(format(A[q], 'b'))
        b = list(reversed(b))
        for i in range(len(b)):
            if b[i] == '1':
                S[i] += 1
        q += 1
    ans += q-p
    if p == q:
        q += 1
    else:
        b = list(format(A[p], 'b'))
        b = list(reversed(b))
        for i in range(len(b)):
            if b[i] == '1':
                S[i] -= 1
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

ans = 0
S = A[0]
right = 1
for l, a in enumerate(A):
    while right < N and S + A[right] == S ^ A[right]:
        S += A[right]
        right += 1
    ans += right - l
    S -= a

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
A = list(map(int, input().split()))
acc = [0]

for Ai in A:
    acc.append(acc[-1]+Ai)
    
ans = 0
r = 0
xor = 0

for l in range(N):
    while r<N and xor^A[r]==acc[r+1]-acc[l]:
        xor ^= A[r]
        r += 1
    
    ans += r-l
    
    if l==r:
        r += 1
    else:
        xor ^= A[l]

print(ans)

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    sumA = [0] * (N + 1)
    for i, a in enumerate(A): sumA[i+1] = sumA[i] + a

    left, right = 0, 1
    count = 0
    current = A[0]
    while left < N:
        count += right - left
        while right < N:
            if current ^ A[right] == sumA[right + 1] - sumA[left]:
                count += 1
                current ^= A[right]
                right += 1
            else: break
        current ^= A[left]
        left += 1
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
N = int(input())
A = list(map(int, input().split(' ')))

r, x = 0, 0
ans = 0
for l in range(0, N):
    while r < N and not (x & A[r]):
        x ^= A[r]
        r += 1
    ans += r - l
    x ^= A[l]
print(ans)

Solution (Python):

def main():
    N = int(input())
    A = list(map(int, input().split()))
    l = 0
    ans = 0
    t = 0
    for i, v in enumerate(A):
        if t & v == 0:
            t |= v
        else:
            while t & v > 0:
                t ^= A[l]
                l += 1
            t |= v
        ans += i - l + 1
    return ans
print(main())

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

ans = 0
r = -1
xor_n = 0
sum_n = 0
for l in range(n):
    while True:
        r += 1

        if r < n:
            nr = a[r]
            xor_n ^= nr
            sum_n += nr
            ok = xor_n == sum_n
        if r >= n or not ok:
            ans += (r - 1) - l + 1
            sum_n -= nr
            sum_n -= a[l]
            xor_n ^= nr
            xor_n ^= a[l]
            r -= 1
            break
print(ans)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int,input().split()))
    cnt = 0
    t = 0
    r = 0
    for l in range(N):
        while r < N and (t & A[r]) == 0:
            t += A[r]
            r += 1
        t -= A[l]
        cnt += (r-l)

    print(cnt)

main()

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
cnt = 0
t = 0
r = 0
for l in range(N):
    while r < N and (t & A[r]) == 0:
        t += A[r]
        r += 1
    t -= A[l]
    cnt += (r-l)

print(cnt)

Solution (Python):


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
s = 0
t = 0
xs = a[0]
ss = a[0]
    
ans = 0
for s in range(n):
    while xs==ss:
        if t<n-1 and xs^a[t+1]==ss+a[t+1]:
            t += 1
            xs ^= a[t]
            ss += a[t]
        else:
            break
    ans += (t-s+1)
    xs ^= a[s]
    ss -= a[s]
print(ans)

Solution (Python):



N = int(input())
A = list(map(int, input().split()))


"""
a xor b と　a+b の比較
・a+bには桁上がりがあるが、a xor bにはないので、　a+b >= a xor b
　等号が成立するのは、aとbの各bitで一致するものがないときか。

毎回bitごとに確認して被ったら左端のやつを除外して～はしんどいので、普通に累積和とxorでよさそう
a+b = a xor b なら、(a+b) xor c = (a xor b) xor c　なので、基本的に累積和管理でOK
"""


ans = 0
total = 0
r = 0
for l in range(N):
    while r <= N-1 and total + A[r] == total ^ A[r]:
        total += A[r]
        r += 1
        

    ans += r-l
    
    total -= A[l]        

print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
bit = [-1] * 40
c = 0
m = -1
for i in range(n):
  cur = bin(a[i])[2::]
  cur = cur[::-1]
  for j,k in enumerate(cur):
    if k == '1':
      m = max(m,bit[j])
      bit[j] = i
  bit = [j if j>m else -1 for j in bit]
  c += i-(m+1)
print(c+n)