Sasha likes programming. Once, during a very long contest, Sasha decided that he was a bit tired and needed to relax. So he did. But since Sasha isn't an ordinary guy, he prefers to relax unusually. During leisure time Sasha likes to upsolve unsolved problems because upsolving is very useful.

Therefore, Sasha decided to upsolve the following problem:

You have an array $a$ with $n$ integers. You need to count the number of funny pairs $(l, r)$ $(l \leq r)$. To check if a pair $(l, r)$ is a funny pair, take $mid = \frac{l + r - 1}{2}$, then if $r - l + 1$ is an even number and $a_l \oplus a_{l+1} \oplus \ldots \oplus a_{mid} = a_{mid + 1} \oplus a_{mid + 2} \oplus \ldots \oplus a_r$, then the pair is funny. In other words, $\oplus$ of elements of the left half of the subarray from $l$ to $r$ should be equal to $\oplus$ of elements of the right half. Note that $\oplus$ denotes the bitwise XOR operation.

It is time to continue solving the contest, so Sasha asked you to solve this task.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 3 \cdot 10^5$) — the size of the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^{20}$) — array itself.


-----Output-----

Print one integer — the number of funny pairs. You should consider only pairs where $r - l + 1$ is even number.


-----Examples-----
Input
5
1 2 3 4 5

Output
1

Input
6
3 2 2 3 7 6

Output
3

Input
3
42 4 2

Output
0



-----Note-----

Be as cool as Sasha, upsolve problems!

In the first example, the only funny pair is $(2, 5)$, as $2 \oplus 3 = 4 \oplus 5 = 1$.

In the second example, funny pairs are $(2, 3)$, $(1, 4)$, and $(3, 6)$.

In the third example, there are no funny pairs.

Difficulty: competition

Starter code:

Solutions:
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
from collections import Counter as C
n = ii()
a = li()
oe = [C(), C()]
oe[1][0] = 1
x = 0
ans = 0
for i in range(n):
    x ^= a[i]
    ans += oe[i % 2][x]
    oe[i % 2][x] += 1
print(ans)

maxn = int(3e5) + 3
maxa = (1 << 20) + 3
nb_element = int(input())
arr = [int(x) for x in input().split()]
cnt = [[0 for _ in range(maxa)] for _ in range(2)]
cnt[1][0] = 1
xors = 0
res = 0
for i in range(nb_element):
    xors ^= arr[i]
    x  = i % 2
    res += cnt[x][xors]
    cnt[x][xors] += 1
print(res)

n = int(input())
l = list(map(int, input().strip().split()))
even = [0 for i in range(2**21)]
odd = [0 for i in range(2**21)]
cur = 0
even[0] = 1
for i in range(n):
    cur = cur^l[i]
    if i%2:
        even[cur] += 1
    else:
        odd[cur] += 1
ans = 0
for i in range(2**21):
    if even[i] >= 2: ans += (even[i]*(even[i]-1))/2
    if odd[i] >= 2: ans += (odd[i]*(odd[i]-1))/2
print(int(ans))


'''
n=int(input())
a=list(map(int,input().split()))#a^b^b=a，b^b=0
def lastcount(r):
    nonlocal a
    right=a[r]
    left=a[r-1]
    i=r
    j=r-1
    k=0
    while j>=0:
        k+=left==right
        j-=2
        i-=1
        left=left^a[i]^a[j]^a[j+1]
        right=right^a[i]
    return k
dp=0
for i in range(n-1,0,-1):
    dp+=lastcount(i)
print(dp)
'''
n=int(input())
a=list(map(int,input().split()))
o={}
e={}
t=a[0]
e[t]=1
o[0]=1
ans,i=0,1
odd=True
while i<n:
    t^=a[i]
    if odd:
        ans+=o.get(t,0)
        o[t]=o.get(t,0)+1
    else:
        ans+=e.get(t,0)
        e[t]=e.get(t,0)+1
    i+=1
    odd=1-odd
print(ans)
    



n = int(input())
a = [int(x) for x in input().split()]
pred = [0]
for i in range(n):
    pred.append(a[i] ^ pred[-1])
d = {}
d1 = {}
a = pred[::2]
b = pred[1::2]
ans = 0
for i in a:
    d[i] = d.get(i, 0) + 1
for i in b:
    d1[i] = d1.get(i, 0) + 1
for i in d:
    ans += d[i] * (d[i] - 1) // 2
for i in d1:
    ans += d1[i] * (d1[i] - 1) // 2
print(ans)

n = int(input())
a = list(map(int, input().split()))
prev = [0]

for i in range(n):
	prev.append(a[i] ^ prev[-1])

var = {}
var1 = {}
a = prev[::2]
b = prev[1::2]
ans = 0

for c in a:
	var[c] = var.get(c, 0) + 1

for x in b:
	var1[x] = var1.get(x, 0) + 1

for c in var:
	ans += var[c] * (var[c] - 1) // 2

for c in var1:
	ans += var1[c] * (var1[c] - 1) // 2

print(ans)


n=int(input())
nlist=[int(x) for x in input().split()]
xor=[[0]*2**21 for xor in range(2)]
x=counter=0
xor[1][0]=1
for i in range(n):
    x^=nlist[i]
    counter+=xor[i%2][x]
    xor[i%2][x]+=1
print(counter)


import math
import sys
from bisect import bisect_right, bisect_left, insort_right
from collections import Counter, defaultdict
from heapq import heappop, heappush
from itertools import accumulate, permutations, combinations
from sys import stdout

R = lambda: map(int, input().split())
n = int(input())
dp = defaultdict(lambda: [0, 0])
dp[0] = [1, 0]
xor = res = 0
for i, x in enumerate(R()):
    xor ^= x
    res += dp[xor][(i + 1) & 1]
    dp[xor][(i + 1) & 1] += 1
print(res)

from collections import Counter

n = int(input())
a = [*map(int, input().split())]

pre = [[0] * (2 ** 20), [1] + [0] * (2 ** 20 - 1)]
t = ans = 0

for i in range(n):
    t ^= a[i]
    ans += pre[i & 1][t]
    pre[i & 1][t] += 1

print(ans)

def count(arr):
    even = 0
    odd = 0
    for i in arr:
        if i % 2 == 1:
            even += 1
        else:
            odd += 1
    return (even-1) * even //2 + (odd - 1) * odd //2

def solve(a):
    sums = []
    x = 0
    for i in a:
        x = x ^ i
        sums.append(x)
    # print(sums)
    d = {}
    d[0] = [-1]
    for i in range(len(sums)):
        if sums[i] in d:
            d[sums[i]].append(i)
        else:
            d[sums[i]] = [i]
    # print(d)
    res = 0
    for sums in d:
        res += count(d[sums])
    return res

n = int(input())
x = input().split()
a = []
for i in x:
    a.append(int(i))
print(solve(a))


n=int(input())
g=[int(g) for g in input().split()]
xor=0
arr=[[0]*(2**20),[1]+[0]*(2**20-1)]
count=0
for i in range(len(g)):
    xor^=g[i]
    count+=arr[i%2][xor]
    arr[i%2][xor]+=1
print(count)


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

dp = [[0 for _ in range(1 << 20)] for _ in range(2)]
dp[1][0] = 1
xor = 0
ret = 0
for i in range(n):
    xor ^= a[i]
    ret += dp[i & 1][xor]
    dp[i & 1][xor] += 1
print(ret)


from collections import Counter

def check_funny(n, nums):
    cnt = {0: Counter(), 1: Counter()}
    cnt[1][0] = 1
    x = 0
    res = 0
    for i in range(n):
        x ^= nums[i]
        res += cnt[i % 2][x]
        cnt[i % 2][x] += 1
    return res


n = int(input())
nums = list(map(int, input().split()))
print(check_funny(n, nums))


from collections import Counter
n = int(input())
x = [0]
for v in map(int, input().split()):
    x.append(x[-1] ^ v)
c0 = Counter(x[::2])
c1 = Counter(x[1::2])
r = 0
for v in c0.values():
    r += v*(v-1)//2
for v in c1.values():
    r += v*(v-1)//2
print(r)    

n, d, curr = int(input()), {(0, 1) : 1}, 0
for i, e in enumerate(map(int, input().split())):
    curr ^= e
    p = (curr, i & 1)
    d[p] = d.get(p, 0) + 1
res = sum((n * (n - 1)) // 2 for n in list(d.values()))
print(res)


from itertools import accumulate
from collections import Counter
from operator import xor
print(sum((n * (n - 1)) // 2 for n in list((Counter((i & 1, e) for i, e in enumerate(accumulate([list(map(int, input().split())) for _ in range(2)][1], xor))) + Counter([(1, 0)])).values())))


n = int(input())
a = [int(x) for x in input().split()]
cnt = [[0, 0] for x in range((1 << 20) + 3)]
cnt[0][1] = 1
x = 0
res = 0
for j in range(n):
    x ^= a[j]
    res += cnt[x][j % 2]
    cnt[x][j % 2] += 1
print(res)


from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
s = [0]
for i in range(N):
    s.append(s[-1] ^ a[i])

D1 = defaultdict(int)
D2 = defaultdict(int)
ans = 0
for i in range(N + 1):
    if i % 2 == 0:
        ans += D1[s[i]]
        D1[s[i]] += 1
    else:
        ans += D2[s[i]]
        D2[s[i]] += 1


print(ans)

n = int(input())
a = list(map(int,input().split()))
preXor = [0]*n
preXor[0] = a[0]
for i in range(1,n):
    preXor[i] = a[i]^preXor[i-1]
even = {}
odd = {}
count = 0
for i in range(n):
    m = preXor[i]
    if (m==0):
        if (i%2==1):
            count += 1
    if (i%2==0):
        if m in even:
            count += even[m]
            even[m] += 1
        else:
            even[m] = 1
    else:
        if m in odd:
            count += odd[m]
            odd[m] += 1
        else:
            odd[m] = 1
print(count)


n = int(input())
a = list(map(int, input().split()))
a = [0] + a

x = [0] * (n+1)
c = {0:1}
sol = 0
for i in range(1, n+1):
    x[i] = x[i-1] ^ a[i]
    if x[i]*2 + i%2 in c:
        sol += c[x[i]*2 + i%2]
    try:
        c[x[i]*2 + i%2] += 1
    except KeyError:
        c[x[i]*2 + i%2] = 1

print(sol)


from math import *
from collections import *
import sys
sys.setrecursionlimit(10**9)
  
n = int(input())
a = list(map(int,input().split()))
pre = [0]
for i in range(n):
	pre.append(pre[-1]^a[i])
de = dict()
do = dict()
for i in range(n+1):
	if(i % 2 == 0):
		if pre[i] not in de:
			de[pre[i]] = 1
		else:
			de[pre[i]] += 1
	else:
		if pre[i] not in do:
			do[pre[i]] = 1
		else:
			do[pre[i]] += 1
ans = 0
for x in list(de.values()): 
	ans += x*(x-1)//2
for x in list(do.values()): 
	ans += x*(x-1)//2
print(ans)


n = int(input())
a = list(map(int,input().split()))
xor = 0
arr=[[0]*(2**20),[1]+[0]*(2**20-1)]
count = 0
for i in range(n):
    xor = xor^a[i]
    count += arr[i%2][xor]
    arr[i%2][xor]+=1
print(count)

n=int(input())
pref=[0]
app=pref.append
for i,x in enumerate(map(int,input().split())):
    app(pref[-1]^x)
d,di={},{}
for i,x in enumerate(pref):
    if i%2==0:
        if d.get(x)==None:d[x]=0
        d[x]+=1
    else:
        if di.get(x)==None:di[x]=0
        di[x]+=1
res=0
for i,x in enumerate(d):res+=(d[x]*(d[x]-1)//2)
for i,x in enumerate(di):res+=(di[x]*(di[x]-1)//2)
print(res)

n=int(input())
pref=[0]
app=pref.append
for i,x in enumerate(map(int,input().split())):
    app(pref[-1]^x)
from collections import Counter
d=Counter(pref[::2])
di=Counter(pref[1::2])
res=0
for i,x in enumerate(d):res+=(d[x]*(d[x]-1)//2)
for i,x in enumerate(di):res+=(di[x]*(di[x]-1)//2)
print(res)

n=int(input())
pref=[0]
app=pref.append
for i,x in enumerate(map(int,input().split())):app(pref[-1]^x)
from collections import Counter
d=Counter(pref[::2])
di=Counter(pref[1::2])
res=0
for i,x in enumerate(d.values()):res+=(x*(x-1)//2)
for i,x in enumerate(di.values()):res+=(x*(x-1)//2)
print(res)