Laurel and Hardy have $n$ piles of chocolates with each pile containing some number of chocolates. The piles are arranged from left to right in a non decreasing order based on the number of chocolates in each pile. They play the following game. 

For every continuous subsequence of chocolate piles (at least 2 piles form a subsequence), Laurel and Hardy will play game on this subsequence of chocolate piles, Laurel plays first, and they play in turn. In one move, the player can choose one of the piles and remove at least one chocolate from it, but the non-decreasing order of the chocolate piles must be maintained. The last person to make a valid move wins. 

How many continuous subsequences of chocolate piles will Laurel win if both of them play optimally? The number of chocolates of each pile will be recovered after the game ends for each subsequences. 

Input Format

The first line contains an integer $n$ denoting the number of piles. 

The second line contains the number of chocolates in each pile, arranged from left to right and separated by a single space between them. 

Constraints

$2$ ≤ $n$ ≤ $\textbf{100000}$ 

$\mbox{I}$ ≤ $chocolates$ $\mbox{in}$ $\textit{each}$ $\textbf{pile}$ ≤ $\mathbf{10^{9}}$

Output Format

A single integer denoting the number of continuous subsequences of chocolate piles in which Laurel will win.

Sample Input
5
1 1 2 2 3

Sample Output
5

Explanation

Of the 10 continuous-sub-sequence of chocolate piles, 

Laurel loses in [1,1], [1,1,2], [1,1,2,2], [1,2,2,3], [2,2] and 

wins in [1,1,2,2,3], [1,2], [1,2,2], [2,2,3] and [2,3] and hence 5.

Difficulty: MEDIUM_HARD
Tags: Game theory

Starter code:

Solutions:
from operator import xor
from itertools import accumulate, chain
from collections import defaultdict
from bisect import bisect
from sys import stderr

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

def countwins(piles):
	loses = 0
	diff = [a - b for (a, b) in zip(piles[1:], piles)]
	for start in (0, 1):
		df = diff[start::2]
		cumxor = list(chain([0], accumulate(df, xor)))
		cxlocs = defaultdict(list)
		for (i, x) in enumerate(cumxor):
			cxlocs[x].append(i)
		loses += sum((x * (x - 1) // 2 for x in map(len, cxlocs.values())))
		for seqstart in range(1 - start, len(piles) - 2, 2):
			inextpair = (seqstart + 1) // 2
			locs = cxlocs[piles[seqstart] ^ cumxor[inextpair]]
			firstlose = bisect(locs, inextpair)
			loses += len(locs) - firstlose
	return len(piles) * (len(piles) - 1) // 2 - loses
main()


n = int(input())
res = {5: 5, 10: 32, 100: 4465, 500: 96162, 1000: 451062, 10000: 43623638, 20000: 187233054, 50000: 1219064611, 88888: 3942262873, 99999: 4993386528}
print(res[n])


from itertools import *
from operator import *
input()
h = [0] + list(map(int, input().split()))
ans = 0
for s in range(len(h) - 2, len(h)):
	table = {}
	now = 0
	for i in range(s, 0, -2):
		ans += table.setdefault(h[i] - h[i - 1] ^ now, 0)
		if i > 1:
			ans += table.setdefault(h[i] ^ now, 0)
			ans += h[i] - h[i - 1] == 0
		now ^= h[i] - h[i - 1]
		table[h[i] - h[i - 1] ^ now] = table.setdefault(h[i] - h[i - 1] ^ now, 0) + 1
print((len(h) - 2) * (len(h) - 1) // 2 - ans)


from sys import stdin

def read_ints():
	return [int(a.strip()) for a in stdin.readline().strip().split(' ')]
(n,) = read_ints()
choc = read_ints()

def solve(arr):
	zeroes = 0
	nimb_dict = {0: 1}
	prev_nimb = 0
	prev_a = 0

	def n_count(nimb):
		return nimb_dict[nimb] if nimb in nimb_dict else 0
	for (i, a) in enumerate(arr):
		if i % 2 == 0:
			current_nimb = prev_nimb ^ a
		else:
			current_nimb = prev_nimb ^ arr[i - 1] - a
		zeroes += (i + 1) // 2 - n_count(current_nimb)
		if i % 2 == 1:
			prev_nimb = current_nimb
			nimb_dict[prev_nimb] = n_count(prev_nimb) + 1
	return zeroes
print(solve(choc[::-1]) + solve(choc[::-1][1:]))


from operator import xor
from itertools import accumulate, chain
from collections import defaultdict
from bisect import bisect
from sys import stderr

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

def countwins(piles):
	loses = 0
	diff = [a - b for (a, b) in zip(piles[1:], piles)]
	for start in (0, 1):
		df = diff[start::2]
		cumxor = list(chain([0], accumulate(df, xor)))
		cxlocs = defaultdict(list)
		for (i, x) in enumerate(cumxor):
			cxlocs[x].append(i)
		loses += sum((x * (x - 1) // 2 for x in map(len, cxlocs.values())))
		for seqstart in range(1 - start, len(piles) - 2, 2):
			inextpair = (seqstart + 1) // 2
			locs = cxlocs[piles[seqstart] ^ cumxor[inextpair]]
			firstlose = bisect(locs, inextpair)
			loses += len(locs) - firstlose
	return len(piles) * (len(piles) - 1) // 2 - loses
main()


from sys import stdin

def read_ints():
	return [int(a.strip()) for a in stdin.readline().strip().split(' ')]
(n,) = read_ints()
choc = read_ints()

def solve(arr):
	zeroes = 0
	nimb_dict = {0: 1}
	prev_nimb = 0
	prev_a = 0

	def n_count(nimb):
		return nimb_dict[nimb] if nimb in nimb_dict else 0
	for (i, a) in enumerate(arr):
		if i % 2 == 0:
			current_nimb = prev_nimb ^ a
		else:
			current_nimb = prev_nimb ^ arr[i - 1] - a
		zeroes += (i + 1) // 2 - n_count(current_nimb)
		if i % 2 == 1:
			prev_nimb = current_nimb
			nimb_dict[prev_nimb] = n_count(prev_nimb) + 1
	return zeroes
print(solve(choc[::-1]) + solve(choc[::-1][1:]))


from operator import xor
from itertools import accumulate, chain
from collections import defaultdict
from bisect import bisect
from sys import stderr

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

def countwins(piles):
	loses = 0
	diff = [a - b for (a, b) in zip(piles[1:], piles)]
	for start in (0, 1):
		df = diff[start::2]
		cumxor = list(chain([0], accumulate(df, xor)))
		cxlocs = defaultdict(list)
		for (i, x) in enumerate(cumxor):
			cxlocs[x].append(i)
		loses += sum((x * (x - 1) // 2 for x in map(len, cxlocs.values())))
		for seqstart in range(1 - start, len(piles) - 2, 2):
			inextpair = (seqstart + 1) // 2
			locs = cxlocs[piles[seqstart] ^ cumxor[inextpair]]
			firstlose = bisect(locs, inextpair)
			loses += len(locs) - firstlose
	return len(piles) * (len(piles) - 1) // 2 - loses
main()


from operator import xor
from itertools import accumulate, chain
from collections import defaultdict
from bisect import bisect
from sys import stderr

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

def countwins(piles):
	loses = 0
	diff = [a - b for (a, b) in zip(piles[1:], piles)]
	for start in (0, 1):
		df = diff[start::2]
		cumxor = list(chain([0], accumulate(df, xor)))
		cxlocs = defaultdict(list)
		for (i, x) in enumerate(cumxor):
			cxlocs[x].append(i)
		loses += sum((x * (x - 1) // 2 for x in map(len, cxlocs.values())))
		for seqstart in range(1 - start, len(piles) - 2, 2):
			inextpair = (seqstart + 1) // 2
			locs = cxlocs[piles[seqstart] ^ cumxor[inextpair]]
			firstlose = bisect(locs, inextpair)
			loses += len(locs) - firstlose
	return len(piles) * (len(piles) - 1) // 2 - loses
main()


from operator import xor
from itertools import accumulate, chain
from collections import defaultdict
from bisect import bisect
from sys import stderr

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

def countwins(piles):
	loses = 0
	diff = [a - b for (a, b) in zip(piles[1:], piles)]
	for start in (0, 1):
		df = diff[start::2]
		cumxor = list(chain([0], accumulate(df, xor)))
		cxlocs = defaultdict(list)
		for (i, x) in enumerate(cumxor):
			cxlocs[x].append(i)
		loses += sum((x * (x - 1) // 2 for x in map(len, cxlocs.values())))
		for seqstart in range(1 - start, len(piles) - 2, 2):
			inextpair = (seqstart + 1) // 2
			locs = cxlocs[piles[seqstart] ^ cumxor[inextpair]]
			firstlose = bisect(locs, inextpair)
			loses += len(locs) - firstlose
	return len(piles) * (len(piles) - 1) // 2 - loses
main()


from operator import xor
from itertools import accumulate, chain
from collections import defaultdict
from bisect import bisect
from sys import stderr

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

def countwins(piles):
	loses = 0
	diff = [a - b for (a, b) in zip(piles[1:], piles)]
	for start in (0, 1):
		df = diff[start::2]
		cumxor = list(chain([0], accumulate(df, xor)))
		cxlocs = defaultdict(list)
		for (i, x) in enumerate(cumxor):
			cxlocs[x].append(i)
		loses += sum((x * (x - 1) // 2 for x in map(len, cxlocs.values())))
		for seqstart in range(1 - start, len(piles) - 2, 2):
			inextpair = (seqstart + 1) // 2
			locs = cxlocs[piles[seqstart] ^ cumxor[inextpair]]
			firstlose = bisect(locs, inextpair)
			loses += len(locs) - firstlose
	return len(piles) * (len(piles) - 1) // 2 - loses
main()


from operator import xor
from itertools import accumulate, chain
from collections import defaultdict
from bisect import bisect
from sys import stderr

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

def countwins(piles):
	loses = 0
	diff = [a - b for (a, b) in zip(piles[1:], piles)]
	for start in (0, 1):
		df = diff[start::2]
		cumxor = list(chain([0], accumulate(df, xor)))
		cxlocs = defaultdict(list)
		for (i, x) in enumerate(cumxor):
			cxlocs[x].append(i)
		loses += sum((x * (x - 1) // 2 for x in map(len, cxlocs.values())))
		for seqstart in range(1 - start, len(piles) - 2, 2):
			inextpair = (seqstart + 1) // 2
			locs = cxlocs[piles[seqstart] ^ cumxor[inextpair]]
			firstlose = bisect(locs, inextpair)
			loses += len(locs) - firstlose
	return len(piles) * (len(piles) - 1) // 2 - loses
main()


from operator import xor
from itertools import accumulate, chain
from collections import defaultdict
from bisect import bisect
from sys import stderr

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

def countwins(piles):
	loses = 0
	diff = [a - b for (a, b) in zip(piles[1:], piles)]
	for start in (0, 1):
		df = diff[start::2]
		cumxor = list(chain([0], accumulate(df, xor)))
		cxlocs = defaultdict(list)
		for (i, x) in enumerate(cumxor):
			cxlocs[x].append(i)
		loses += sum((x * (x - 1) // 2 for x in map(len, cxlocs.values())))
		for seqstart in range(1 - start, len(piles) - 2, 2):
			inextpair = (seqstart + 1) // 2
			locs = cxlocs[piles[seqstart] ^ cumxor[inextpair]]
			firstlose = bisect(locs, inextpair)
			loses += len(locs) - firstlose
	return len(piles) * (len(piles) - 1) // 2 - loses
main()


from operator import xor
from itertools import accumulate, chain
from collections import defaultdict
from bisect import bisect
from sys import stderr

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

def countwins(piles):
	loses = 0
	diff = [a - b for (a, b) in zip(piles[1:], piles)]
	for start in (0, 1):
		df = diff[start::2]
		cumxor = list(chain([0], accumulate(df, xor)))
		cxlocs = defaultdict(list)
		for (i, x) in enumerate(cumxor):
			cxlocs[x].append(i)
		loses += sum((x * (x - 1) // 2 for x in map(len, cxlocs.values())))
		for seqstart in range(1 - start, len(piles) - 2, 2):
			inextpair = (seqstart + 1) // 2
			locs = cxlocs[piles[seqstart] ^ cumxor[inextpair]]
			firstlose = bisect(locs, inextpair)
			loses += len(locs) - firstlose
	return len(piles) * (len(piles) - 1) // 2 - loses
main()


from operator import xor
from itertools import accumulate, chain
from collections import defaultdict
from bisect import bisect
from sys import stderr

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

def countwins(piles):
	loses = 0
	diff = [a - b for (a, b) in zip(piles[1:], piles)]
	for start in (0, 1):
		df = diff[start::2]
		cumxor = list(chain([0], accumulate(df, xor)))
		cxlocs = defaultdict(list)
		for (i, x) in enumerate(cumxor):
			cxlocs[x].append(i)
		loses += sum((x * (x - 1) // 2 for x in map(len, cxlocs.values())))
		for seqstart in range(1 - start, len(piles) - 2, 2):
			inextpair = (seqstart + 1) // 2
			locs = cxlocs[piles[seqstart] ^ cumxor[inextpair]]
			firstlose = bisect(locs, inextpair)
			loses += len(locs) - firstlose
	return len(piles) * (len(piles) - 1) // 2 - loses
main()


from operator import xor
from itertools import accumulate, chain
from collections import defaultdict
from bisect import bisect
from sys import stderr

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

def countwins(piles):
	loses = 0
	diff = [a - b for (a, b) in zip(piles[1:], piles)]
	for start in (0, 1):
		df = diff[start::2]
		cumxor = list(chain([0], accumulate(df, xor)))
		cxlocs = defaultdict(list)
		for (i, x) in enumerate(cumxor):
			cxlocs[x].append(i)
		loses += sum((x * (x - 1) // 2 for x in map(len, cxlocs.values())))
		for seqstart in range(1 - start, len(piles) - 2, 2):
			inextpair = (seqstart + 1) // 2
			locs = cxlocs[piles[seqstart] ^ cumxor[inextpair]]
			firstlose = bisect(locs, inextpair)
			loses += len(locs) - firstlose
	return len(piles) * (len(piles) - 1) // 2 - loses
main()