Dexter and Debra are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where i^{th} container has A[i] number of chocolates.

The game goes like this. First player will choose a container and take one or more chocolates from it. Then, second player will choose a non-empty container and take one or more chocolates from it. And then they alternate turns. This process will continue, until one of the players is not able to take any chocolates (because no chocolates are left). One who is not able to take any chocolates loses the game. Note that player can choose only non-empty container.

The game between Dexter and Debra has just started, and Dexter has got the first Chance. He wants to know the number of ways to make a first move such that under optimal play, the first player always wins.

Input Format

The first line contains an integer N, i.e., number of containers. 

The second line contains N integers, i.e., number of chocolates in each of the containers separated by a single space.  

Constraints

$1 ≤ N ≤ 10^{6} $

$1 ≤ A[i] ≤ 10^{9} $

Output Format

Print the number of ways to make the first move such that under optimal play, the first player always wins. If the first player cannot win under optimal play, print 0.  

Sample Input
2
2 3

Sample Output
1

Explanation

Only 1 set of moves helps player 1 win. 

Player:      1      2      1      2      1
Chocolates: 2 3 -> 2 2 -> 1 2 -> 1 1 -> 0 1

Source: hackerrank | Difficulty: MEDIUM
Tags: Game theory


Solutions:
from functools import reduce
import operator
n = int(input())
a = list(map(int, input().split()))
gr = reduce(operator.xor, a)
ans = sum((1 for _ in filter(lambda x: x ^ gr < x, a)))
print(ans)


N = int(input())
A = [int(_) for _ in input().split()]
x = 0
for a in A:
	x ^= a
if x == 0:
	print(0)
else:
	n = 0
	for a in A:
		if a ^ x < a:
			n += 1
	print(n)


N = int(input())
A = list(map(int, input().split()))
xor = 0
for a in A:
	xor ^= a
if xor == 0:
	print(0)
else:
	ans = 0
	for a in A:
		if xor ^ a <= a:
			ans += 1
	print(ans)


from functools import reduce
N = int(input())
arr = list(map(int, list(input().split())))
nim = reduce(lambda x, y: x ^ y, arr)
print(sum(map(lambda x: 1 if x - (nim ^ x) > 0 else 0, arr)))


from functools import reduce
n = int(input())
nums = [int(val) for val in input().split()]
nimSum = reduce(lambda x, y: x ^ y, nums)
if nimSum == 0:
	print(0)
else:
	print(len(list(filter(lambda x: x > x ^ nimSum, nums))))


from functools import reduce
N = int(input())
heaps = list(map(int, input().strip().split()))
nim = reduce(lambda x, y: x ^ y, heaps)
if nim == 0:
	num = 0
else:
	num = 0
	for n in heaps:
		if n ^ nim < n:
			num = num + 1
print(num)


n = int(input())
arr = list(map(int, input().split()))
xor = 0
res = 0
for a in arr:
	xor ^= a
while xor & xor - 1:
	xor = xor & xor - 1
if not xor:
	print(0)
	exit(0)
for a in arr:
	if xor & a:
		res += 1
print(res)


num_heaps = input()
heaps = input().split()
winning = int(heaps[0])
new_heaps = heaps[1:]
for heap in new_heaps:
	winning = winning ^ int(heap)
count = 0
for heap in heaps:
	if int(heap) > winning ^ int(heap):
		count += 1
print(count)


from functools import reduce
from operator import xor

def main():
	ncont = int(input())
	a = [int(f) for f in input().split()]
	assert len(a) == ncont
	print(countwins(a))

def countwins(a):
	xorall = reduce(xor, a)
	return sum((xorall ^ e < e for e in a))
main()


from functools import reduce
nimbers = []
input()
piles = list(map(int, input().split()))
xor = lambda x: reduce(lambda x, y: x ^ y, x)
nim_sum = xor(piles)
count = 0
if nim_sum != 0:
	for i in piles:
		if i ^ nim_sum < i:
			count += 1
print(count)


n = int(input())
a = list(map(int, input().split()))
r = 0
count = 0
for x in a:
	r = r ^ x
for x in a:
	ra = r ^ x
	if ra <= x:
		count += 1
if r:
	print(count)
else:
	print('0')


N = int(input())
A = [int(i) for i in input().split()]

def nim_sum(ar):
	result = 0
	for a in ar:
		result ^= a
	return result
nim_sum = 0
for a in A:
	nim_sum ^= a
count = 0
for a in A:
	nim_sum_tmp = nim_sum ^ a
	if nim_sum_tmp < a:
		count += 1
print(count)


from functools import reduce

def find_win(ls):
	res = reduce(lambda x, y: x ^ y, ls, 0)
	return len([i for i in ls if i > res ^ i])
n = int(input())
l = list(map(int, input().split()))
print(find_win(l))


n = int(input())
a = list(map(int, input().split()))
x = 0
for y in a:
	x ^= y
k = [int(x ^ y <= y) for y in a]
print(sum(k) * (x > 0))


import sys
_N = int(sys.stdin.readline())
A = [int(X) for X in sys.stdin.readline().split()]
p = A[0]
for a in A[1:]:
	p ^= a
count = 0
for a in A:
	count += 1 if a ^ p < a else 0
print(count)


import functools
n = int(input())
boxes = list(map(int, input().split()))
nimsum = functools.reduce(lambda x, y: x ^ y, boxes)
newboxes = list(map(lambda x: x ^ nimsum, boxes))
print(sum(list((1 for i in range(len(boxes)) if newboxes[i] < boxes[i]))))


from operator import xor
from functools import reduce

def solve(piles):
	nimSum = reduce(xor, piles)
	total = 0
	for p in piles:
		if xor(p, nimSum) < p:
			total += 1
	return total
input()
print(solve([int(i) for i in input().split(' ')]))


import functools
N = int(input())
A = [int(x) for x in input().split()]
axor = functools.reduce(lambda x, y: x ^ y, A, 0)
res = 0
for a in A:
	if a ^ axor < a:
		res += 1
print(res)


n = int(input())
p = [int(x) for x in input().split()]
s = p[0]
for i in p[1:]:
	s ^= i
sol = 0
if s != 0:
	for i in range(n):
		s ^= p[i]
		if s < p[i]:
			sol += 1
		s ^= p[i]
print(sol)


n = int(input().strip())
a = [int(x) for x in input().split()]
nim = 0
for x in a:
	nim ^= x
cnt = 0
if nim > 0:
	for x in a:
		val = nim ^ x
		if val <= x:
			cnt += 1
print(cnt)


t = int(input())
arr = list(map(int, input().split()))
nim = 0
for a in arr:
	nim ^= a
if nim == 0:
	print(0)
else:
	count = 0
	for a in arr:
		if a ^ nim < a:
			count += 1
	print(count)


n = int(input())
a = list(map(int, input().split()))
x = 0
for i in range(n):
	x = x ^ a[i]
c = 0
if x != 0:
	for i in range(n):
		ans = x ^ a[i]
		if ans < a[i]:
			c = c + 1
print(c)


N = int(input().strip())
containers = input().strip().split()
containers = [int(i) for i in containers]

def nim_sum(val):
	result = 0
	for v in val:
		result ^= v
	return result
n = nim_sum(containers)
if n == 0:
	print(0)
else:
	count = 0
	for choc in containers:
		temp = n ^ choc
		if temp < choc:
			count += 1
	print(count)


N = int(input().strip())
A = list(map(int, input().strip().split(' ')))
Sum = 0
for a in A:
	Sum = Sum ^ a
count = 0
for a in A:
	b = a ^ Sum
	if b < a:
		count += 1
print(count)


from functools import reduce
import operator
N = int(input())
a = list(map(int, input().split()))
res = reduce(operator.xor, a)
if res == 0:
	print(0)
else:
	count = 0
	for value in a:
		if value ^ res < value:
			count += 1
	print(count)


def tel(n=5):
	return [i + 1 for i in range(n)]

def tel2(n=4, m=None):
	if m == None:
		m = n
	return [[i * m + j + 1 for j in range(m)] for i in range(n)]

def tels(n=5):
	return 'abcde' * 2

def abc(n):
	return list(map(chr, range(97, 123)))[n]

def lflat2(l):
	if ist(l[0], list):
		return [x for y in l for x in y]
	else:
		return l

def lflat(l):
	return lflat2(l)

def lflat(l):
	nl = []
	for x in l:
		if type(x) == list:
			nl += lflat(x)
		else:
			nl.append(x)
	return nl

def ist(o, t):
	return isinstance(o, t)

def lm(f, *l):
	return list(map(f, *l))

def specsum(l, f):
	su = l[0]
	for x in l[1:]:
		su = f(su, x)
	return su

def xorsum(l):
	return specsum(l, lambda x, y: int(x) ^ int(y))

def allsteps(l):
	lst = []
	l = lm(int, l)
	nimsum = xorsum(l)
	for (i, x) in enumerate(l):
		dif = nimsum ^ x
		if dif < x:
			lst.append((i, x, dif))
	return lst
n = int(input())
l = input().split()
print(len(allsteps(l)))


import functools

def nim_sum(p):
	return functools.reduce(lambda a, b: a ^ b, p, 0)

def win_cases(p):
	nsum = nim_sum(p)
	return sum([c - (c ^ nsum) > 0 for c in p])
input()
print(win_cases(list(map(int, input().split()))))


n = int(input())
a = [int(i) for i in input().split()]
val = 0
for i in range(n):
	val = val ^ a[i]
result = 0
for i in range(n):
	if val ^ a[i] < a[i]:
		result += 1
print(result)


def main():
	input()
	cs = [int(x) for x in input().split()]
	nimsum = 0
	for s in cs:
		nimsum ^= s
	movs = 0
	for s in cs:
		y = nimsum ^ s
		if y < s:
			movs += 1
	print(movs)
main()


from operator import xor
from functools import reduce
n = int(input())
a = [int(i) for i in input().split()]
x = reduce(xor, a, 0)
s = 0
for heap in a:
	s += 1 if heap ^ x < heap else 0
print(s)


import sys
N = int(input())
iArr = tuple(map(int, input().split()))
toXor = 0
for i in iArr:
	toXor ^= i
if toXor == 0:
	print(0)
	sys.exit()
aCount = 0
for i in iArr:
	if i - (i ^ toXor) >= 0:
		aCount += 1
print(aCount)


N = int(input())
heaps = tuple((int(x) for x in input().split()))
X = 0
for heap in heaps:
	if heap != 0:
		X ^= heap
if X == 0:
	print(0)
else:
	moves = 0
	for heap in heaps:
		temp = heap ^ X
		if heap != 0 and temp < heap:
			moves += 1
	print(moves)


import functools

def nim(heaps):
	X = functools.reduce(lambda x, y: x ^ y, heaps)
	return 0 if X == 0 else sum([1 for t in heaps if t ^ X < t])
n = int(input().strip())
ar = [int(i) for i in input().strip().split()]
print(nim(ar))


N = int(input())
xor_sum = 0
heaps = list(map(int, input().split()))
for heap in heaps:
	xor_sum ^= heap
if xor_sum == 0:
	print(0)
else:
	result = 0
	for heap in heaps:
		if heap ^ xor_sum < heap:
			result += 1
	print(result)


c = int(input())
heaps = list(map(int, input().split(' ')))

def func():
	X = heaps[0]
	for heap in heaps[1:]:
		X = X ^ heap
	if X == 0:
		if max(heaps) > 1:
			return 0
		return len([heap for heap in heaps if heap > 0])
	else:
		sums = [t ^ X < t for t in heaps]
		chosen_heap = sums.index(True)
		nb_remove = heaps[chosen_heap] - (heaps[chosen_heap] ^ X)
		heaps_twomore = 0
		for (i, heap) in enumerate(heaps):
			n = heap - nb_remove if chosen_heap == i else heap
			if n > 1:
				heaps_twomore += 1
		if heaps_twomore == 0:
			return len([heap for heap in heaps if heap == max(heaps)])
		else:
			return len(list(filter(lambda x: x, sums)))
print(func())


(n, a, b) = (input(), list(map(int, input().split())), 0)
for i in a:
	b ^= i
print(sum([int(i ^ b < i) for i in a]))


(n, a, b) = (input(), list(map(int, input().split())), 0)
for i in a:
	b ^= i
print(sum([int(i ^ b < i) for i in a]))


import functools
n = int(input())
boxes = list(map(int, input().split()))
nimsum = functools.reduce(lambda x, y: x ^ y, boxes)
newboxes = list(map(lambda x: x ^ nimsum, boxes))
print(sum(list((1 for i in range(len(boxes)) if newboxes[i] < boxes[i]))))


n = int(input())
hps = input().split()
s = 0
for i in hps:
	s ^= int(i)
ways = 0
for i in hps:
	x = int(i)
	if x > x ^ s:
		ways += 1
print(ways)


import functools
n = int(input())
boxes = list(map(int, input().split()))
nimsum = functools.reduce(lambda x, y: x ^ y, boxes)
newboxes = list(map(lambda x: x ^ nimsum, boxes))
print(sum(list((1 for i in range(len(boxes)) if newboxes[i] < boxes[i]))))


from functools import reduce
N = int(input())
A = [int(x) for x in input().split(' ')]
grundy = reduce(lambda x, y: x ^ y, A)
winning_moves = sum((grundy ^ x < x for x in A))
print(winning_moves)


n = input().strip()
s = input().strip().split(' ')
n = int(n)
s = [int(x) for x in s]
l = 0
co = 0
for i in s:
	k = l ^ i
	l = k
for i in s:
	if int(i ^ l) < i:
		co += 1
print(co)


n = int(input().strip())
l = list(map(int, input().strip().split(' ')))
xor = 0
r = 0
for num in l:
	xor ^= num
if xor == 0:
	print(r)
else:
	for i in range(0, n):
		xor ^= l[i]
		if xor == 0:
			r += 1
		elif xor <= l[i]:
			r += 1
		xor ^= l[i]
	print(r)


numPiles = int(input())
piles = [int(pile) for pile in input().split(' ')]
xor = 0
for pile in piles:
	xor ^= pile
if xor == 0:
	print('0')
else:
	count = 0
	for pile in piles:
		if xor ^ pile in range(pile):
			count += 1
	print(count)


from functools import reduce
from operator import xor

def solve(chocolates):
	g = reduce(xor, chocolates)
	return sum([int(i ^ g < i) for i in chocolates])

def main():
	n = input()
	chocolates = list(map(int, input().split()))
	print(solve(chocolates))
main()


from functools import reduce

def count_moves(heaps):
	game_sum = reduce(lambda x, y: x ^ y, heaps)
	count = 0
	for heap_size in heaps:
		if heap_size ^ game_sum < heap_size:
			count += 1
	return count
n = int(input())
heaps = [int(x) for x in input().split(' ')]
print(count_moves(heaps))


from functools import reduce
from operator import xor
input()
A = [int(x) for x in input().strip().split(' ')]
xorsum = reduce(xor, A)
print(sum((a ^ xorsum < a for a in A)))


n = int(input())
a = [int(num) for num in input().split()]
x = a[0]
l = len(a)
for i in range(1, l):
	x = x ^ a[i]
c = 0
for i in range(l):
	if x ^ a[i] < a[i]:
		c = c + 1
print(c)


from functools import reduce

def gh(x, k):
	r = max(0, x - (x ^ k))
	return 1 if r != 0 else 0
(n, a) = (int(input()), list((int(x) for x in input().strip().split())))
k = reduce(lambda x, y: x ^ y, a)
print(sum((gh(x, k) for x in a)))


from functools import reduce
n = input()
if n == 1:
	print(1)
	exit(0)
a = list(map(int, input().split()))
val = reduce(lambda x, y: x ^ y, a)
answer = 0
if val == 0:
	print(0)
	exit(0)
for ele in a:
	if ele ^ val <= ele:
		answer += 1
print(answer)


n = input()
a = [int(i) for i in input().split()]
b = 0
for i in a:
	b ^= i
print(sum([int(i ^ b < i) for i in a]))


n = int(input())
l = list(map(int, input().split(' ')))
a = 0
b = 0
for i in range(n):
	a ^= l[i]
for j in range(n):
	if a ^ l[j] < l[j]:
		b += 1
print(b)


from operator import xor
from functools import reduce
(_, ar) = (input(), tuple(map(int, input().split())))
move = reduce(xor, ar, 0)
print(sum((x >= move ^ x for x in ar)) if move else 0)


heaps = int(input())
boxes = []
X = 0
for i in input().strip().split():
	boxes.append(int(i))
	X ^= int(i)
counter = 0
for j in boxes:
	if X ^ j < j:
		counter += 1
print(counter)


n = int(input())
A = list(map(int, input().split()))
s = 0
for pile in A:
	s ^= pile
if s == 0:
	print(0)
else:
	result = 0
	for pile in A:
		result += int(pile ^ s < pile)
	print(result)


n = int(input())
a = [int(x) for x in input().strip().split(' ')]
total = a[0]
for i in range(1, n):
	total = total ^ a[i]
count = 0
for i in range(0, n):
	if total ^ a[i] < a[i]:
		count += 1
print(count)


from functools import reduce
from operator import xor

def main(a):
	value = reduce(xor, a)
	if value == 0:
		return 0
	return sum((1 for h in a if value ^ h < h))
input()
print(main(tuple((int(s) for s in input().split()))))


def fast_nim(inputs):
	b = 0
	for i in inputs:
		b ^= i
	return sum([int(i ^ b < i) for i in inputs])
n = input()
a = [int(i) for i in input().split()]
print(fast_nim(a))


n = int(input())
a = [int(x) for x in input().split(' ')]
xa = 0
for x in a:
	xa ^= x
turns = sum((1 for x in a if x ^ xa < x))
print(turns)


n = int(input().strip())
bit_xor = 0
vals = [int(x) for x in input().strip().split()]
for val in vals:
	bit_xor ^= val
if bit_xor == 0:
	print(0)
else:
	count = -1
	while bit_xor != 0:
		count += 1
		bit_xor >>= 1
	bit_xor = 1 << count
	count = 0
	for val in vals:
		if bit_xor & val != 0:
			count += 1
	print(count)


n = int(input())
l = [int(x) for x in input().split()]
s = 0
for i in l:
	s ^= i
if s == 0:
	print(s)
	exit(0)
c = 0
for i in l:
	if i ^ s < i:
		c += 1
print(c)


N = int(input())
C = [int(x) for x in input().split()]
x = 0
for i in range(len(C)):
	x = x ^ C[i]
if x == 0:
	print(0)
else:
	ans = bin(x)[2:]
	Cbits = [bin(x)[2:] for x in C]
	w2w = 0
	for k in range(len(Cbits)):
		if len(Cbits[k]) >= len(ans) and Cbits[k][-len(ans)] == '1':
			w2w += 1
	print(w2w)


from functools import reduce
from operator import xor
input()
a = [int(x) for x in input().split()]
tot = reduce(xor, a)
print(sum((tot ^ x < x for x in a)))


n = int(input())
c = [int(s) for s in input().split()]
d = {}
for i in c:
	k = 0
	for j in bin(i)[::-1]:
		if j == 'b':
			break
		if j == '1':
			try:
				d[k] += 1
			except:
				d[k] = 1
		k += 1
win = False
k = sorted(d.keys(), reverse=True)
for i in k:
	if d[i] % 2 != 0:
		print(d[i])
		win = True
		break
if not win:
	print(0)


n = int(input())
a = [int(ai) for ai in input().strip().split(' ')]
x = a[0]
s = 0
for i in range(1, n):
	x = x ^ a[i]
for i in range(n):
	if x ^ a[i] < a[i]:
		s = s + 1
print(s)


N = int(input())
array = [int(x) for x in input().split()]
result = 0
for elt in array:
	result ^= elt
if result == 0:
	print(0)
else:
	count = 0
	for elt in array:
		tmp = elt ^ result
		if elt >= tmp:
			count += 1
	print(count)


n = int(input().strip())
a = [int(temp) for temp in input().strip().split(' ')]
if n == 1:
	print(1)
else:
	score = 0
	count = 0
	for atemp in a:
		score ^= atemp
	if score == 0:
		print(0)
	else:
		leading_one = 0
		while score:
			score //= 2
			leading_one += 1
		possible_moves = 0
		leading_two = 2 ** (leading_one - 1)
		for atemp in a:
			if atemp & leading_two:
				possible_moves += 1
		print(possible_moves)


(n, a, b) = (input(), input().split(), 0)
a = [int(e) for e in a]
for i in a:
	b ^= i
print(sum([int(i ^ b < i) for i in a]))


(n, c) = (int(input()), 0)
a = list(map(int, input().split()))
for i in a:
	c ^= i
if c == 0:
	print('0')
	exit()
s = 0
for i in range(n):
	l = c ^ a[i]
	if l < a[i]:
		s += 1
print(s)


import functools
boxes = int(input().strip())
heaps = [int(a_temp) for a_temp in input().strip().split(' ')]
outp = functools.reduce(lambda x, y: x ^ y, heaps)
if outp == 0:
	print(0)
else:
	i = 0
	for h in heaps:
		if h ^ outp < h:
			i = i + 1
	print(i)


n = int(input().strip())
arr = list(map(int, input().strip().split(' ')))
nim_sum = 0
for i in arr:
	nim_sum = nim_sum ^ i
valid_moves = 0
for i in arr:
	if i > i ^ nim_sum:
		valid_moves += 1
print(valid_moves)


N = input()
A = input()
A = A.split()
A = [int(i) for i in A]

def nimsum(A):
	x = 0
	for a in A:
		x = int(bin(a ^ x), 2)
	return x
nA = nimsum(A)
if nA == 0:
	print(0)
else:
	s = 0
	for a in A:
		if int(bin(a ^ nA), 2) < a:
			s = s + 1
	print(s)


n = int(input())
a = [int(i) for i in input().split()]
result = 0
for i in a:
	result = result ^ i
print(sum([int(i ^ result < i) for i in a]))


N = int(input())
A = list(map(int, input().split()))
g = 0
for i in A:
	g ^= i
if g == 0:
	print(0)
else:
	digit = len(str(bin(g))) - 2
	res = [x for x in A if len(bin(x)) - 2 >= digit]
	print(len([x for x in res if bin(x)[-digit] == '1']))


from functools import reduce

def game(n, a):
	xors = reduce(lambda acc, x: acc ^ x, a)
	if xors == 0:
		return 0
	assert xors > 0
	while xors & xors - 1 > 0:
		xors &= xors - 1
	assert xors & xors - 1 == 0
	ans = 0
	for e in a:
		if e & xors > 0:
			ans += 1
	return ans

def main():
	n = int(input())
	a = list(map(int, input().split()))
	print(game(n, a))
main()


from functools import reduce
from operator import xor
_ = int(input())
s = tuple(map(int, input().split()))
w = reduce(xor, s)
cnt = sum((w ^ k < k for k in s))
print(cnt)


from functools import reduce
N = int(input())
A = [int(A_temp) for A_temp in input().split(' ')]
X = reduce(lambda a, b: a ^ b, A)
print(sum([int(X ^ i < i) for i in A]))


n = int(input().strip())
arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
if n == 0:
	print(0)
r = 0
for i in arr:
	r = r ^ i
if r == 0:
	print(0)
else:
	s = [r ^ i for i in arr]
	j = 0
	for i in range(n):
		if arr[i] >= s[i]:
			j += 1
	print(j)


n = int(input())
a = map(int, input().strip().split())
xor = 0
b = []
for k in a:
	b.append(k)
	xor ^= k
win = 0
if xor != 0:
	for k in b:
		if k >= k ^ xor:
			win += 1
print(win)


from functools import reduce
n = int(input().strip())
ar = list(map(int, input().strip().split(' ')))
xr = reduce(lambda x, y: x ^ y, ar)
xr_list = [d ^ xr for d in ar]
num_moves = sum([1 for (a, b) in zip(ar, xr_list) if a - b > 0])
print(num_moves)


n = int(input())
a = list(map(int, input().split()))
import functools as ft
r = ft.reduce(lambda x, y: x ^ y, a, 0)
if r == 0:
	print(0)
else:
	q = bin(r)[2:]
	l = len(q) - 1
	res = 0
	for i in a:
		if i >> l & 1 == 1:
			res += 1
	print(res)


boxes = int(input())
lis = [int(x) for x in input().strip().split()]
nimsum = 0
for i in lis:
	nimsum ^= i
if nimsum == 0:
	print(0)
else:
	ways = 0
	for i in lis:
		if i ^ nimsum < i:
			ways += 1
	print(ways)


import sys
n = input().strip()
arr = list(map(int, input().strip().split(' ')))
possible = 0
for i in arr:
	possible = possible ^ i
print(sum([int(i ^ possible < i) for i in arr]))


n = int(input())
a = [int(x) for x in input().split()]
tot = 0
for x in a:
	tot = tot ^ x
if tot == 0:
	print(0)
else:
	ans = 0
	for x in a:
		if x ^ tot <= x:
			ans += 1
	print(ans)


(n, a, b) = (int(input()), list(map(int, input().split())), 0)
for i in a:
	b ^= i
print(sum([int(i ^ b < i) for i in a]))


def winning_moves(chocs):
	nim = chocs[0]
	win = 0
	for i in range(1, len(chocs)):
		nim = nim ^ chocs[i]
	for c in chocs:
		if nim ^ c < c:
			win = win + 1
	return win

def main():
	containers = input()
	choccolates = str(input()).split()
	choccolates = list(map(int, choccolates))
	print(winning_moves(choccolates))
main()


(n, a, b) = (eval(input()), list(map(int, input().split())), 0)
for i in a:
	b ^= i
print(sum([int(i ^ b < i) for i in a]))


(_, A) = (input(), [int(i) for i in input().strip().split()])
x = 0
for a in A:
	x ^= a
print(len([1 for a in A if a ^ x < a]))


n_boxes = int(input().strip())
boxes = [int(i) for i in input().strip().split(' ')]

def move(boxes, player1=True, first_move=True):
	count = 0
	nim_sum = 0
	for box in boxes:
		nim_sum ^= box
	for box in boxes:
		if box > box ^ nim_sum:
			count += 1
	return count
print(move(boxes))


(n, a, b) = (input(), list(map(int, input().split())), 0)
for i in a:
	b ^= i
print(sum([int(i ^ b < i) for i in a]))


input()
data = [int(x) for x in input().split(' ')]
(xsum, c) = (0, 0)
for x in data:
	xsum ^= x
if x == 0:
	print(0)
else:
	for x in data:
		if x > xsum ^ x:
			c += 1
	print(c)