Yurii is sure he can do everything. Can he solve this task, though?

He has an array $a$ consisting of $n$ positive integers. Let's call a subarray $a[l...r]$ good if the following conditions are simultaneously satisfied:   $l+1 \leq r-1$, i. e. the subarray has length at least $3$;  $(a_l \oplus a_r) = (a_{l+1}+a_{l+2}+\ldots+a_{r-2}+a_{r-1})$, where $\oplus$ denotes the bitwise XOR operation. 

In other words, a subarray is good if the bitwise XOR of the two border elements is equal to the sum of the rest of the elements. 

Yurii wants to calculate the total number of good subarrays. What is it equal to?

An array $c$ is a subarray of an array $d$ if $c$ can be obtained from $d$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.


-----Input-----

The first line contains a single integer $n$ ($3 \leq n \leq 2\cdot 10^5$) — the length of $a$. 

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \lt 2^{30}$) — elements of $a$. 


-----Output-----

Output a single integer — the number of good subarrays. 


-----Examples-----
Input
8
3 1 2 3 1 2 3 15

Output
6
Input
10
997230370 58052053 240970544 715275815 250707702 156801523 44100666 64791577 43523002 480196854

Output
2


-----Note-----

There are $6$ good subarrays in the example:   $[3,1,2]$ (twice) because $(3 \oplus 2) = 1$;  $[1,2,3]$ (twice) because $(1 \oplus 3) = 2$;  $[2,3,1]$ because $(2 \oplus 1) = 3$;  $[3,1,2,3,1,2,3,15]$ because $(3 \oplus 15) = (1+2+3+1+2+3)$.

Difficulty: MEDIUM

Starter code:

Solutions:
def solve(a):
	seen = set()
	for i in range(len(a)):
		c = 0
		for j in range(i + 2, len(a)):
			c += a[j - 1]
			if a[i] ^ a[j] == c:
				seen.add((i, j))
			if c >= 2 * a[i]:
				break
	for i in range(len(a) - 1, -1, -1):
		c = 0
		for j in range(i - 2, -1, -1):
			c += a[j + 1]
			if a[i] ^ a[j] == c:
				seen.add((j, i))
			if c >= 2 * a[i]:
				break
	print(len(seen))
n = int(input())
solve(list(map(int, input().split())))


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

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

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

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

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None
t = 1
for i in range(t):
	n = N()
	a = RLL()
	ans = 0
	for j in range(2):
		pre = [0]
		for i in range(n):
			pre.append(pre[-1] + a[i])
		for i in range(n - 2):
			k = len(bin(a[i])) - 2
			k = 1 << k
			for r in range(i + 2, n):
				if pre[r] - pre[i + 1] > k:
					break
				if a[i] > a[r] and a[i] ^ a[r] == pre[r] - pre[i + 1]:
					ans += 1
		a = a[::-1]
	print(ans)


import itertools, math
n = int(input())
A = list(map(int, input().split()))
acc = [0] + list(itertools.accumulate(A))
ans = 0
seen = set()
for i in range(n - 2):
	a = int(math.log2(A[i]))
	for j in range(i + 2, n):
		cur = acc[j] - acc[i + 1]
		b = int(math.log2(cur))
		if b > a:
			break
		if A[i] ^ A[j] == cur and (i, j) not in seen:
			ans += 1
			seen.add((i, j))
for j in range(n - 1, 1, -1):
	a = int(math.log2(A[j]))
	for i in range(j - 2, -1, -1):
		cur = acc[j] - acc[i + 1]
		b = int(math.log2(cur))
		if b > a:
			break
		if A[i] ^ A[j] == cur and (i, j) not in seen:
			ans += 1
			seen.add((i, j))
print(ans)


n = int(input())
a = list(map(int, input().split(' ')))
ans = 0
for i in range(n):
	sum = 0
	for j in range(i + 2, n, 1):
		sum += a[j - 1]
		if sum >= a[i] + a[i]:
			break
		if a[i] ^ a[j] == sum and a[i] >= a[j]:
			ans += 1
for i in range(n):
	sum = 0
	for j in range(i - 2, -1, -1):
		sum += a[j + 1]
		if sum >= a[i] + a[i]:
			break
		if a[i] ^ a[j] == sum and a[i] > a[j]:
			ans += 1
print(ans)


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

def calc(a):
	ans = 0
	for i in range(2, len(a)):
		sum = 0
		for j in reversed(range(0, i - 1)):
			sum += a[j + 1]
			ans += a[i] > a[j] and a[i] ^ a[j] == sum
			if sum > 2 * a[i] or a[j].bit_length() > a[i].bit_length():
				break
	return ans
print(calc(a) + calc(a[::-1]))


import sys
try:
	(sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))
except:
	pass
ii1 = lambda : int(sys.stdin.readline().strip())
is1 = lambda : sys.stdin.readline().strip()
iia = lambda : list(map(int, sys.stdin.readline().strip().split()))
isa = lambda : sys.stdin.readline().strip().split()
mod = int(1000000000.0 + 7)
from collections import *
from math import *
from itertools import *
from functools import *
n = ii1()
arr = iia()
ans = 0
for l in range(30):
	for i in range(n):
		if arr[i] & 1 << l:
			currsum = 0
			for j in range(i + 2, n):
				currsum += arr[j - 1]
				if currsum >= 2 << l:
					break
				if currsum < 1 << l:
					continue
				if arr[i] ^ arr[j] == currsum:
					ans += 1
			currsum = 0
			for j in range(i - 2, -1, -1):
				currsum += arr[j + 1]
				if currsum >= 2 << l:
					break
				if currsum < 1 << l:
					continue
				if arr[i] ^ arr[j] == currsum:
					ans += 1
print(ans)


def f(a):
	ans = 0
	for i in range(n - 2):
		s = 0
		for j in range(i + 2, n):
			s += a[j - 1]
			ans += a[i] > a[j] and a[i] ^ a[j] == s
			if s > 2 * a[i]:
				break
	return ans
read = lambda : map(int, input().split())
n = int(input())
a = list(read())
print(f(a) + f(a[::-1]))


import math
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(2, n):
	sum = 0
	for j in reversed(range(0, i - 1)):
		sum += a[j + 1]
		ans += a[i] > a[j] and a[i] ^ a[j] == sum
		if sum > 2 * a[i] or a[j].bit_length() > a[i].bit_length():
			break
a.reverse()
for i in range(2, n):
	sum = 0
	for j in reversed(range(0, i - 1)):
		sum += a[j + 1]
		ans += a[i] >= a[j] and a[i] ^ a[j] == sum
		if sum > 2 * a[i] or a[j].bit_length() > a[i].bit_length():
			break
print(ans)


from sys import *
input = stdin.readline

def solve(n, a, t):
	ans = 0
	for i in range(n):
		sum = 0
		high1 = a[i].bit_length() - 1
		for j in range(i + 1, n - 1):
			high2 = a[j + 1].bit_length() - 1
			sum += a[j]
			if sum >= 1 << high1 + 1:
				break
			if a[i] ^ a[j + 1] == sum and (t == 0 or high1 != high2):
				ans += 1
	return ans
n = int(input())
a = list(map(int, input().split()))
ans = solve(n, a, 0)
a = a[::-1]
ans += solve(n, a, 1)
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
ans = set([])
for i in range(n):
	x = 1
	while x <= a[i]:
		x *= 2
	j = i + 1
	sum = 0
	while j < n - 1 and sum < x:
		sum += a[j]
		if a[i] ^ a[j + 1] == sum:
			ans.add(n * i + j + 1)
		j += 1
	sum = 0
	j = i - 1
	while j > 0 and sum < x:
		sum += a[j]
		if a[i] ^ a[j - 1] == sum:
			ans.add(n * (j - 1) + i)
		j -= 1
print(len(ans))