AtCoder Beginner Contest 172 - Unfair Nim

There are N piles of stones. The i-th pile has A_i stones.
Aoki and Takahashi are about to use them to play the following game:
 - Starting with Aoki, the two players alternately do the following operation:
 - Operation: Choose one pile of stones, and remove one or more stones from it.
 - When a player is unable to do the operation, he loses, and the other player wins.
When the two players play optimally, there are two possibilities in this game: the player who moves first always wins, or the player who moves second always wins, only depending on the initial number of stones in each pile.
In such a situation, Takahashi, the second player to act, is trying to guarantee his win by moving at least zero and at most (A_1 - 1) stones from the 1-st pile to the 2-nd pile before the game begins.
If this is possible, print the minimum number of stones to move to guarantee his victory; otherwise, print -1 instead.

-----Constraints-----
 - 2 \leq N \leq 300
 - 1 \leq A_i \leq 10^{12}

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 \ldots A_N

-----Output-----
Print the minimum number of stones to move to guarantee Takahashi's win; otherwise, print -1 instead.

-----Sample Input-----
2
5 3

-----Sample Output-----
1

Without moving stones, if Aoki first removes 2 stones from the 1-st pile, Takahashi cannot win in any way.
If Takahashi moves 1 stone from the 1-st pile to the 2-nd before the game begins so that both piles have 4 stones, Takahashi can always win by properly choosing his actions.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
import sys
from functools import lru_cache
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(N, *A) = map(int, read().split())
(a, b) = A[:2]
xor = 0
for x in A[2:]:
	xor ^= x
INF = 10 ** 13

@lru_cache(None)
def F(a, b, xor):
	if a & 1 ^ b & 1 != xor & 1:
		return INF
	if xor == 0:
		return INF if a < b else (a - b) // 2
	x = 2 * F(a // 2, b // 2, xor // 2)
	y = 2 * F((a - 1) // 2, (b + 1) // 2, xor // 2) + 1
	x = min(x, y)
	if x >= INF:
		x = INF
	return x
x = F(a, b, xor)
if x >= a:
	x = -1
print(x)


import sys
sys.setrecursionlimit(300000)

def solve(N: int, A: 'List[int]'):

	def _to_bits(v):
		xb = []
		h = {}
		i = 0
		while v > 0:
			xb.append((2 ** i, v % 2))
			h[2 ** i] = v % 2
			v //= 2
			i += 1
		return (xb, h)
	xor = 0
	for i in range(2, N):
		xor ^= A[i]
	s = A[0] + A[1]
	rest = s - xor
	if rest < 0 or rest % 2 or rest // 2 > A[0]:
		ret = -1
	else:
		ret = 0
		rest //= 2
		(xb, xx) = _to_bits(xor)
		(rb, rr) = _to_bits(rest)
		for (k, v) in rr.items():
			if v == 1 and k in xx and (xx[k] == 1):
				ret = -1
				print(ret)
				return
		xb.reverse()
		tmp = rest
		for (base, v) in xb:
			if v and tmp + base < A[0]:
				tmp += base
		if tmp > 0:
			ret = A[0] - tmp
		else:
			ret = -1
	print(ret)
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	A = [int(next(tokens)) for _ in range(N)]
	solve(N, A)
main()


import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n, *a) = map(int, read().split())
v = 0
for i in a[2:]:
	v ^= i
w = a[0] + a[1]
z = w - v
if z & 1 == 1 or z < 0:
	print(-1)
else:
	z //= 2
	if z & v:
		print(-1)
		exit()
	ans = z
	for i in range(60, -1, -1):
		m = 1 << i
		if v & m:
			if ans + m <= a[0]:
				ans += m
	if ans > a[0] or ans == 0:
		print(-1)
	else:
		print(a[0] - ans)


from collections import defaultdict
mem = defaultdict(lambda : None)
mem[0, 0, 0] = 0

def dp(a, b, s):
	if mem[a, b, s] is not None:
		return mem[a, b, s]
	x = a & 1
	y = b & 1
	xor = s & 1
	res = float('inf')
	if x ^ y != xor:
		mem[a, b, s] = res
		return res
	else:
		res = 2 * dp(a >> 1, b >> 1, s >> 1)
		if a > 1:
			pants = 2 * dp(a - 1 >> 1, b + 1 >> 1, s >> 1) + 1
			if pants < res:
				res = pants
	mem[a, b, s] = res
	return res
n = int(input())
a = list(map(int, input().split()))
s = 0
for i in a[2:]:
	s ^= i
b = a[1]
a = a[0]
ans = dp(a, b, s)
if ans == float('inf'):
	ans = -1
print(ans)


import sys

def main(N, A):
	xor = 0
	for i in range(2, N):
		xor ^= A[i]
	p = A[0] + A[1]
	if p - xor & 1:
		return -1
	a = p - xor >> 1
	bl = max(A[0], xor).bit_length()
	dp = [[-1] * 2 for _ in range(bl + 1)]
	dp[0][0] = 0
	az = A[0]
	for i in range(bl):
		ni = i + 1
		azb = az & 1
		xorb = xor & 1
		ab = a & 1
		for j in range(2):
			if dp[i][j] < 0:
				continue
			for nazb in range(2):
				if nazb > azb:
					nj = 1
				elif nazb < azb:
					nj = 0
				else:
					nj = j
				for nbzb in range(2):
					if nazb ^ nbzb == xorb and nazb & nbzb == ab:
						break
				else:
					continue
				dp[ni][nj] = max(dp[ni][nj], dp[i][j] | nazb << i)
		az >>= 1
		xor >>= 1
		a >>= 1
	ans = dp[bl][0]
	if ans <= 0:
		return -1
	return A[0] - ans
input = sys.stdin.readline
N = int(input())
(*A,) = map(int, input().split())
print(main(N, A))


import sys, queue, math, copy, itertools, bisect, collections, heapq

def main():
	LI = lambda : [int(x) for x in sys.stdin.readline().split()]
	NI = lambda : int(sys.stdin.readline())
	N = NI()
	A = LI()
	x = 0
	for i in A[2:]:
		x ^= i
	s = A[0] + A[1]
	if s - x < 0 or (s - x) % 2:
		print(-1)
		return
	a = (s - x) // 2
	if a & x:
		print(-1)
		return
	b = 1 << A[0].bit_length() - 1
	while b > 0:
		if b & x and a + b <= A[0]:
			a += b
		b >>= 1
	if 0 < a <= A[0]:
		print(A[0] - a)
	else:
		print(-1)
main()


import bisect
N = int(input())
A = list(map(int, input().split()))
x = 0
for i in range(2, N):
	x ^= A[i]
if (A[0] + A[1] - x) % 2 != 0:
	print(-1)
else:
	AND = (A[0] + A[1] - x) // 2
	u = AND
	v = AND
	if AND & x != 0:
		print(-1)
		exit()
	t = [i for i in range(40) if x >> i & 1 == 1]
	k = len(t) // 2
	data1 = []
	data2 = []
	for i in range(2 ** k):
		temp = 0
		for j in range(k):
			if i >> j & 1 == 1:
				temp += 2 ** t[j]
		data1.append(temp)
	for i in range(2 ** (len(t) - k)):
		temp = 0
		for j in range(len(t) - k):
			if i >> j & 1 == 1:
				temp += 2 ** t[k + j]
		data2.append(temp)
	ans = -1
	val = float('inf')
	for test in data1:
		temp = test + u
		id = bisect.bisect_right(data2, A[0] - temp)
		if id != 0:
			temp += data2[id - 1]
			if val > A[0] - temp and A[0] >= temp and (temp != 0):
				val = A[0] - temp
				ans = temp
		elif val > A[0] - temp and A[0] >= temp and (temp != 0):
			val = A[0] - temp
			ans = temp
	if val != float('inf'):
		print(val)
	else:
		print(-1)


def main():
	import sys

	def input():
		return sys.stdin.readline().rstrip()
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	for i in range(2, n):
		x ^= a[i]
	d = a[0] + a[1] - x
	if d % 2 == 1 or d < 0:
		print(-1)
		return
	d >>= 1
	if d & x != 0 or d > a[0]:
		print(-1)
		return
	k = x.bit_length()
	tmp = d
	for i in range(k, -1, -1):
		if x >> i & 1:
			if tmp + (1 << i) <= a[0]:
				tmp += 1 << i
	if 0 < tmp <= a[0]:
		print(a[0] - tmp)
	else:
		print(-1)
main()


import numpy as np
LI = lambda : list(map(int, input().split()))
N = int(input())
A = LI()

def main():
	s = 0
	for a in A[2:]:
		s ^= a
	t = A[0] + A[1]
	f = lambda x: list(map(int, format(x, '050b')[::-1]))
	sb = f(s)
	tb = f(t)
	ab = f(A[0])
	dp = np.full((51, 2, 2), -1, dtype=int)
	dp[0][0][0] = 0
	for i in range(50):
		for j in range(2):
			for k in range(2):
				if dp[i][j][k] == -1:
					continue
				for na in range(2):
					for nb in range(2):
						if na ^ nb != sb[i] or (na + nb + j) % 2 != tb[i]:
							continue
						nj = (na + nb + j) // 2
						if na == ab[i]:
							nk = k
						elif na == 1:
							nk = 1
						else:
							nk = 0
						v = dp[i][j][k] + 2 ** i * na
						dp[i + 1][nj][nk] = max(dp[i + 1][nj][nk], v)
	if dp[-1][0][0] < 1:
		ans = -1
	else:
		ans = A[0] - dp[-1][0][0]
	print(ans)

def __starting_point():
	main()
__starting_point()


def examA():
	N = I()
	ans = N + N ** 2 + N ** 3
	print(ans)
	return

def examB():
	S = SI()
	T = SI()
	ans = 0
	for (s, t) in zip(S, T):
		if s != t:
			ans += 1
	print(ans)
	return

def examC():
	(N, M, K) = LI()
	A = LI()
	B = LI()
	SA = 0
	b = 0
	SB = 0
	for i in range(M):
		if SB + B[i] > K:
			break
		SB += B[i]
		b += 1
	ans = 0
	ans = max(ans, b)
	for i in range(N):
		SA += A[i]
		if SA + SB > K:
			while b >= 0:
				if SA + SB <= K:
					break
				SB -= B[b - 1]
				b -= 1
		if b == -1:
			break
		ans = max(ans, b + i + 1)
	print(ans)
	return

def examD():

	def primes(n):
		is_prime = [True] * (n + 1)
		is_prime[0] = False
		is_prime[1] = False
		for i in range(2, int(n ** 0.5) + 1):
			if not is_prime[i]:
				continue
			for j in range(i * 2, n + 1, i):
				is_prime[j] = False
		return [i for i in range(n + 1) if is_prime[i]]
	N = I()
	P = primes(N)
	D = [1] * (N + 1)
	for p in P:
		for i in range(1, 1 + N // p):
			cnt = 1
			cur = i
			while cur % p == 0:
				cnt += 1
				cur //= p
			D[p * i] *= 1 + cnt
	ans = 0
	for i in range(1, N + 1):
		ans += i * D[i]
	print(ans)
	return

def examE():

	class combination:

		def __init__(self, n, mod):
			self.n = n
			self.mod = mod
			self.fac = [1] * (n + 1)
			self.inv = [1] * (n + 1)
			for j in range(1, n + 1):
				self.fac[j] = self.fac[j - 1] * j % mod
			self.inv[n] = pow(self.fac[n], mod - 2, mod)
			for j in range(n - 1, -1, -1):
				self.inv[j] = self.inv[j + 1] * (j + 1) % mod

		def comb(self, n, r):
			if r > n or n < 0 or r < 0:
				return 0
			return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
	(N, M) = LI()
	dp = [0] * (N + 1)
	dp[2] = 1
	for n in range(3, N + 1):
		dp[n] += (dp[n - 1] + dp[n - 2]) * (n - 1)
		dp[n] %= mod
	C = combination(M, mod)
	Acur = C.fac[M]
	Acur %= mod
	for i in range(1, N + 1):
		cur = C.comb(N, i) * C.fac[M - i] * C.inv[M - N]
		cur %= mod
		if i % 2 == 1:
			Acur = Acur + mod - cur
		else:
			Acur = Acur + mod + cur
		Acur %= mod
	if N % 2 == 1:
		Acur += 1
	ans = dp[N] * (C.fac[M] * C.inv[M - N])
	ans %= mod
	print(ans)
	return

def examE2():

	class combination:

		def __init__(self, n, mod):
			self.n = n
			self.mod = mod
			self.fac = [1] * (n + 1)
			self.inv = [1] * (n + 1)
			for j in range(1, n + 1):
				self.fac[j] = self.fac[j - 1] * j % mod
			self.inv[n] = pow(self.fac[n], mod - 2, mod)
			for j in range(n - 1, -1, -1):
				self.inv[j] = self.inv[j + 1] * (j + 1) % mod

		def comb(self, n, r):
			if r > n or n < 0 or r < 0:
				return 0
			return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
	(N, M) = LI()
	C = combination(M, mod)
	cnt = 0
	for i in range(N + 1):
		cur = C.comb(N, i) * C.fac[M - i] * C.inv[M - N] % mod
		if i % 2 == 1:
			cnt -= cur
			cnt += mod
			cnt %= mod
		else:
			cnt += cur
			cnt %= mod
	ans = cnt * (C.fac[M] * C.inv[M - N])
	ans %= mod
	print(ans)
	return

def examF():
	bit = 40
	N = I()
	A = LI()
	aim = 0
	start = A[0] + A[1]
	for a in A[2:]:
		aim ^= a
	cnt = 0
	stack = deque()
	candi = []
	for i in range(bit):
		if 1 << i & aim:
			cnt += 1 << i
			candi.append(1 << i)
		else:
			stack.append(1 << i)
	a = 0
	b = 0
	while stack:
		now = stack.pop()
		if cnt + now * 2 <= start:
			cnt += now * 2
			a += now
			b += now
		if cnt == start:
			break
	if start != cnt:
		print(-1)
		return
	if a > A[0]:
		print(-1)
		return
	for c in candi[::-1]:
		if a + c <= A[0]:
			a += c
	ans = A[0] - a
	if ans == A[0]:
		print(-1)
		return
	print(ans)
	return
from decimal import getcontext, Decimal as dec
import sys, bisect, itertools, heapq, math, random
from copy import deepcopy
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def I():
	return int(input())

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

def DI():
	return dec(input())

def LDI():
	return list(map(dec, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet, _ep
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
_ep = dec('0.000000000001')
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}
getcontext().prec = 28
sys.setrecursionlimit(10 ** 7)
examF()


import sys

def solve():
	input = sys.stdin.readline
	N = int(input())
	A = [int(a) for a in input().split()]
	xorR = 0
	for i in range(2, N):
		xorR ^= A[i]
	rbit = [0] * 41
	K = xorR
	for i in range(41):
		rbit[i] = K % 2
		K //= 2
	D = A[0] + A[1] - xorR
	if D < 0 or D % 2 == 1:
		print(-1)
		return 0
	else:
		D //= 2
		if D > A[0]:
			print(-1)
			return 0
		K = D
		dbit = [0] * 41
		for i in range(41):
			dbit[i] = K % 2
			K //= 2
		A0 = D
		for i in range(41):
			if rbit[40 - i] == dbit[40 - i] and rbit[40 - i] == 1:
				print(-1)
				return 0
			elif rbit[40 - i] == 1:
				if A0 + pow(2, 40 - i) <= A[0]:
					A0 += pow(2, 40 - i)
		if A0 > 0:
			print(A[0] - A0)
		else:
			print(-1)
	return 0

def __starting_point():
	solve()
__starting_point()


import sys
N = int(input())
A = list(map(int, input().split()))
if N == 2:
	if (A[0] + A[1]) % 2 == 1 or A[0] < A[1]:
		print(-1)
	else:
		print((A[0] - A[1]) // 2)
	sys.exit()
S = A[0] + A[1]
X = 0
for i in range(2, N):
	X = X ^ A[i]
D = (S - X) // 2
if (S - X) % 2 == 1 or S - X < 0 or D & X != 0 or (D > A[0]):
	print(-1)
	sys.exit()
Y = 0
for i in range(2, len(bin(X))):
	if bin(X)[i] != '0':
		tmp = 2 ** (len(bin(X)) - i - 1)
		if D ^ tmp + Y <= A[0]:
			Y += tmp
else:
	if Y:
		ans = A[0] - (D ^ Y)
		print(ans)
	else:
		print(-1)


def resolve():
	N = int(input())
	A = list(map(int, input().split()))
	S = A[0] + A[1]
	xor = 0
	for a in A[2:]:
		xor ^= a
	S -= xor
	if S % 2 == 1:
		return print(-1)
	S //= 2
	if S & xor != 0 or S > A[0]:
		return print(-1)
	b = S
	for i in range(41, -1, -1):
		if xor >> i & 1 == 1:
			if b + (1 << i) <= A[0]:
				b += 1 << i
	if b == 0:
		print(-1)
	else:
		print(A[0] - b)

def __starting_point():
	resolve()
__starting_point()


import sys
sys.setrecursionlimit(10 ** 7)

def I():
	return int(sys.stdin.readline().rstrip())

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))
N = I()
A = LI()
a = A[0]
b = A[1]
c = 0
if len(A) >= 3:
	for i in range(2, N):
		c ^= A[i]
INF = 10 ** 12
from functools import lru_cache

@lru_cache(maxsize=None)
def f(s, t, u):
	if s == 0:
		if t == u:
			return 0
		else:
			return INF
	elif s & 1 ^ t & 1 == u & 1:
		return min(2 * f(s // 2, t // 2, u // 2), 2 * f((s - 1) // 2, (t + 1) // 2, u // 2) + 1)
	else:
		return INF
ans = f(a, b, c)
if ans >= a:
	print(-1)
else:
	print(ans)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	A = list(map(int, input().split()))
	if N == 2:
		if A[0] == A[1]:
			print(0)
		elif A[0] < A[1]:
			print(-1)
		elif (A[0] - A[1]) % 2 == 0:
			print((A[0] - A[1]) // 2)
		else:
			print(-1)
		exit()
	g1 = A[0]
	g2 = A[1]
	g3 = 0
	for i in range(2, N):
		g3 ^= A[i]
	n1 = g1.bit_length()
	n2 = g2.bit_length()
	n3 = g3.bit_length()
	NN = max(n1, n2, n3)
	ans = 0
	cnt = 0
	while True:
		cnt += 1
		if cnt == 10000:
			print(-1)
			exit()
		for i in range(NN):
			if g1 >> i & 1 ^ g2 >> i & 1 != g3 >> i & 1:
				r1 = g1 % (1 << i) + 1
				r2 = (1 << i) - g2 % (1 << i)
				if r1 < r2:
					g1 -= r1
					g2 += r1
					ans += r1
					break
				elif r1 > r2:
					g1 -= r2
					g2 += r2
					ans += r2
					break
				else:
					print(-1)
					exit()
			if g1 ^ g2 == g3:
				if ans != A[0]:
					print(ans)
				else:
					print(-1)
				exit()
main()


from functools import reduce
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
r = reduce(lambda x, y: x ^ y, A[2:], 0)
(a, b) = A[:2]

def answer(ta, tb, tr):
	for i in range(ta):
		if ta - i ^ tb + i == tr:
			ans = i
			break
	else:
		ans = -1
	return ans

def solve(a, b, r):
	orga = a
	ans = 0
	l = max(map(lambda x: len(bin(x)), [a, b, r])) - 2
	cand = {(a, b, r): 0}
	for i in range(l):
		temp = defaultdict(lambda : 10 ** 20)
		for ((a, b, r), s) in cand.items():
			(x, y, z) = (a % 2, b % 2, r % 2)
			if not x ^ y == z:
				continue
			else:
				if s < temp[a // 2, b // 2, r // 2]:
					temp[a // 2, b // 2, r // 2] = s
				a -= 1
				b += 1
				if a < 0:
					continue
				s += 1 << i
				if s < temp[a // 2, b // 2, r // 2]:
					temp[a // 2, b // 2, r // 2] = s
		cand = temp
	if not (0, 0, 0) in cand:
		ans = -1
	else:
		ans = cand[0, 0, 0]
		if ans == orga:
			ans = -1
	return ans
print(solve(a, b, r))


n = int(input())
a = list(map(int, input().split()))
al = 0
for i in range(2, n):
	al ^= a[i]
ans = 0
s = a[0] + a[1]
if s - al < 0 or (s - al) % 2:
	ans = -1
else:
	d = (s - al) // 2
	now = d
	for i in range(65, -1, -1):
		if 1 << i & al and (1 << i) + now <= a[0]:
			now += 1 << i
	if now == 0 or now > a[0] or d & al != 0:
		ans = -1
	else:
		ans = a[0] - now
print(ans)


import sys
N = int(input())
A = list(map(int, input().split()))
x = 0
for i in A:
	x ^= i
old = A[0] ^ A[1] ^ x
b0pb1 = A[0] + A[1]
if b0pb1 < old or (b0pb1 - old) % 2 == 1:
	print(-1)
	exit(0)
b0andb1 = (b0pb1 - old) // 2
print(A[0], A[1], b0pb1, old, b0andb1, file=sys.stderr)
if b0andb1 & old != 0:
	print(-1)
	exit(0)
if A[0] < b0andb1:
	print(-1)
	exit(0)
ans = b0andb1
for i in reversed(range(0, 40)):
	if old >> i & 1 == 0:
		continue
	if ans + (1 << i) <= A[0]:
		ans += 1 << i
if ans == 0:
	print(-1)
	exit(0)
print(A[0] - ans)


def main():
	n = int(input())
	a = list(map(int, input().split()))
	(x, y) = (a[0], a[1])
	nim = 0
	for i in range(2, n):
		nim ^= a[i]
	ans = 0
	while x ^ y != nim:
		for i in range(50, -1, -1):
			j = nim >> i & 1
			xy = (x >> i ^ y >> i) & 1
			if j != xy:
				m = min(x % 2 ** i + 1, 2 ** i - y % 2 ** i)
				if x % 2 ** i + 1 == 2 ** i - y % 2 ** i:
					print(-1)
					return
				x -= m
				y += m
				ans += m
				if x <= 0:
					print(-1)
					return
				break
		else:
			if x ^ y != nim:
				print(-1)
				return
	print(ans)
main()


import sys
N_MAX = 200000 + 5
INF = 10 ** 9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10 ** 9 + 7

def main():
	_ = int(sys.stdin.readline().rstrip())
	Arr = [int(x) for x in sys.stdin.readline().rstrip().split()]
	K = 43
	A = Arr[0]
	B = Arr[1]
	S = A + B
	X = 0
	for i in range(2, len(Arr)):
		X ^= Arr[i]
	dp = [[[-1 for x in [0, 1]] for _ in [0, 1]] for _ in range(K)]
	dp[0][0][0] = 0
	v = 1
	for i in range(K - 1):
		cx = X & 1
		cs = S & 1
		ca = A & 1
		for j in range(2):
			for k in range(2):
				if dp[i][j][k] == -1:
					continue
				for na in range(2):
					for nb in range(2):
						ni = i + 1
						nj = 0
						nk = k
						if na ^ nb != cx:
							continue
						ns = na + nb + j
						if ns % 2 != cs:
							continue
						if ns >= 2:
							nj = 1
						if ca < na:
							nk = 1
						elif ca == na:
							nk = k
						else:
							nk = 0
						dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k] | v * na)
		X >>= 1
		S >>= 1
		A >>= 1
		v <<= 1
	a = dp[K - 1][0][0]
	if a == -1 or a == 0:
		print(-1)
	else:
		print(Arr[0] - a)
main()


N = int(input())
A = list(map(int, input().split()))
S = A[0] + A[1]
X = 0
for i in range(2, N):
	X = X ^ A[i]
if (S - X) % 2 == 1 or S < X:
	print(-1)
	return
D = (S - X) // 2
if X & D != 0:
	print(-1)
	return
a = 0
B = [0 for i in range(42)]
for k in range(41, -1, -1):
	x = (X & 1 << k) >> k
	d = (D & 1 << k) >> k
	if (x, d) == (0, 0):
		pass
	elif (x, d) == (0, 1):
		a = a ^ 1 << k
	elif (x, d) == (1, 0):
		B[k] = 1
	else:
		pass
for k in range(41, -1, -1):
	if B[k] == 0:
		continue
	if a ^ 1 << k < A[0]:
		a = a ^ 1 << k
if 0 < a <= A[0]:
	print(A[0] - a)
else:
	print(-1)


from functools import lru_cache

def main():
	N = int(input())
	A = list(map(int, input().split()))
	x = 0
	for a in A[2:]:
		x ^= a
	(a, b) = (A[0], A[1])
	if (a ^ b ^ x) & 1 != 0:
		return -1

	@lru_cache(None)
	def helper(a, b, x):
		if a == 0:
			return 0 if a ^ b == x else None
		if (a ^ b) & 1 != x & 1:
			return None
		t1 = helper(a // 2, b // 2, x // 2)
		t2 = helper((a - 1) // 2, (b + 1) // 2, x // 2)
		if t1 is None and t2 is None:
			return None
		if t1 is None:
			return t2 * 2 + 1
		if t2 is None:
			return t1 * 2
		t1 = t1 * 2
		t2 = t2 * 2 + 1
		return min(t1, t2)
	r = helper(a, b, x)
	if r is None or r >= a:
		return -1
	return r
print(main())


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
a = list(map(int, readline().split()))
s = a[0] + a[1]
if n == 2:
	if a[0] < a[1] or s % 2 == 1:
		print(-1)
	else:
		print(a[0] - s // 2)
	exit()
c = 0
for i in a[2:]:
	c ^= i
sc = (s - c) // 2
if s < c or (s - c) % 2 == 1 or c & sc:
	print(-1)
	exit()
bb = a[0].bit_length()
x = ''
chk = 0
for i in range(bb - 1, -1, -1):
	if not c >> i & 1 | sc >> i & 1:
		x += '0'
	elif not c >> i & 1 and sc >> i & 1:
		x += '1'
		chk += 2 ** i
	else:
		x += '?'
for i in range(bb):
	if x[i] == '?':
		if a[0] >= chk + 2 ** (bb - 1 - i):
			chk += 2 ** (bb - 1 - i)
ans = a[0] - chk
print(ans if a[0] > ans >= 0 else -1)


import sys
n = int(input())
a = list(map(int, input().split()))
c = a[0] + a[1]
t = 0
for ai in a[2:]:
	t = t ^ ai
bit_len = c.bit_length() + 1
if c < t:
	print(-1)
	sys.exit()
if (c - t) % 2:
	print(-1)
	sys.exit()
b1 = (c - t) // 2
a1 = b1
a2 = b1
if a1 > a[0]:
	print(-1)
	sys.exit()
for i in reversed(range(bit_len)):
	if t & 1 << i:
		if b1 & 1 << i:
			print(-1)
			sys.exit()
		if a1 + 2 ** i <= a[0]:
			a1 += 2 ** i
if a1 == 0:
	print(-1)
else:
	print(a[0] - a1)


import math
N = int(input())
A = list(map(int, input().split()))
all_xor = 0
for i in range(N):
	all_xor = all_xor ^ A[i]
fore = A[0] ^ A[1]
back = fore ^ all_xor
a_and_b = (A[0] + A[1] - back) / 2
if a_and_b % 1 != 0 or a_and_b < 0:
	print(-1)
	quit()
a_and_b = int(a_and_b)
if a_and_b & back != 0:
	print(-1)
	quit()
ans = a_and_b
if back == 0:
	if ans == 0:
		print(-1)
	else:
		print(A[0] - ans)
	quit()
else:
	if ans > A[0]:
		print(-1)
		quit()
	nn = int(math.log2(back)) + 1
	for i in range(nn + 1):
		if back >> nn - i & 1:
			k = ans + (1 << nn - i)
			if k <= A[0]:
				ans = k
	if ans == 0:
		print(-1)
	else:
		print(A[0] - ans)


def resolve():
	N = int(input())
	A = [int(a) for a in input().split()]
	x = 0
	for a in A[2:]:
		x ^= a
	s = sum(A[:2])
	if s < x or (s ^ x) & 1:
		print(-1)
		return
	d = (s - x) // 2
	a = A[0]
	n = 0
	for i in range(40)[::-1]:
		(b, c) = (x >> i & 1, d >> i & 1)
		if b == c == 1:
			print(-1)
			return
		if b == 0 and c == 1:
			n += 1 << i
	for i in range(40)[::-1]:
		(b, c) = (x >> i & 1, d >> i & 1)
		if b == 1 and c == 0:
			if n + (1 << i) <= a:
				n += 1 << i
	if n > a or n == 0:
		print(-1)
	else:
		print(a - n)
resolve()


import math
import queue
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)

def main():
	n = int(ipt())
	a = [int(i) for i in ipt().split()]
	x = 0
	for i in a[2:]:
		x ^= i
	s = a[0] + a[1]
	d = (s - x) // 2
	if d < 0 or d & x or s - x & 1 or (d > a[0]):
		print(-1)
		exit()
	a1 = d
	xi = 1
	kx = x
	while kx > 0:
		xi *= 2
		kx >>= 1
	xi //= 2
	while xi > 0:
		if x & xi:
			if a1 + xi <= a[0]:
				a1 += xi
			x -= xi
		xi //= 2
	if a1 == 0:
		print(-1)
		exit()
	else:
		print(a[0] - a1)
	return
main()


import sys
(N,) = map(int, input().split())
X = list(map(int, input().split()))
S = X[0] + X[1]
T = 0
for i in range(2, N):
	T ^= X[i]
if S < T or (S - T) % 2:
	print(-1)
	sys.exit()
D = (S - T) // 2
if D & T:
	print(-1)
	sys.exit()
Y = D
for i in range(T.bit_length() + 1, -1, -1):
	if T & 1 << i | Y <= X[0]:
		Y |= T & 1 << i
if 0 < Y <= X[0]:
	print(X[0] - Y)
else:
	print(-1)


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
con = 10 ** 9 + 7
INF = float('inf')

def getlist():
	return list(map(int, input().split()))

def main():
	N = int(input())
	A = getlist()
	XOR = 0
	for i in range(2, N):
		XOR ^= A[i]
	Asum = A[0] + A[1]
	ans = INF
	AA = Asum
	a0 = 0
	a1 = 0
	for i in range(50, -1, -1):
		if 2 ** i & XOR == 2 ** i:
			AA -= 2 ** i
	for i in range(50, -1, -1):
		if 2 ** i & XOR == 0:
			if AA >= 2 ** (i + 1):
				AA -= 2 ** (i + 1)
				a0 += 2 ** i
				a1 += 2 ** i
			else:
				pass
	for i in range(50, -1, -1):
		if 2 ** i & XOR == 2 ** i:
			if a0 + 2 ** i <= A[0]:
				a0 += 2 ** i
			else:
				a1 += 2 ** i
	if a0 == 0 or a0 > A[0] or a0 + a1 != Asum or (a0 ^ a1 != XOR):
		print(-1)
	else:
		print(A[0] - a0)
main()


def f_unfair_nim():
	from functools import reduce
	from operator import xor
	N = int(input())
	A = [int(i) for i in input().split()]
	s = sum(A[:2])
	x = reduce(xor, A[2:], 0)
	if (s - x) % 2 != 0 or (s - x) // 2 & x != 0:
		return -1
	a = (s - x) // 2
	for i in range(60, -1, -1):
		if x & 1 << i != 0 and a ^ 1 << i <= A[0]:
			a ^= 1 << i
	return A[0] - a if A[0] >= a > 0 else -1
print(f_unfair_nim())


import sys
readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
	n = ni()
	(f, s, *a) = nm()
	x = 0
	for c in a:
		x ^= c
	if (f + s - x) % 2 or (f + s - x) // 2 & x:
		print(-1)
		return
	y = (f + s - x) // 2
	for i in range(40, -1, -1):
		if x & 1 << i and y | 1 << i < f:
			y |= 1 << i
	print(f - y if f >= y > 0 else -1)
	return
solve()


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd, sqrt
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint
sys.setrecursionlimit(2147483647)
INF = 10 ** 20

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

def I():
	return int(sys.stdin.buffer.readline())

def LS():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

def S():
	return sys.stdin.buffer.readline().rstrip().decode('utf-8')

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
n = int(input())
a = list(map(int, input().split()))
t = 0
flg = 0
for ai in a[2:]:
	t = t ^ ai
b1 = a[0] + a[1] - t
if b1 < 0 or b1 % 2:
	flg = 1
b1 //= 2
a1 = b1
if a1 > a[0]:
	flg = 1
for i in reversed(range((a[0] + a[1]).bit_length())):
	if t & 1 << i:
		if b1 & 1 << i:
			flg = 1
		if a1 + 2 ** i <= a[0]:
			a1 += 2 ** i
if a1 == 0:
	flg = 1
print(a[0] - a1 if flg == 0 else -1)


N = int(input())
A = [int(a) for a in input().split()]
t = 0
for a in A[2:]:
	t ^= a
s = sum(A[:2])
if s < t or (s ^ t) & 1:
	print(-1)
	return
u = (s - t) // 2
a = A[0]
n = 0
for i in range(40)[::-1]:
	(b, c) = (t >> i & 1, u >> i & 1)
	if b == c == 1:
		print(-1)
		return
	if b == 0 and c == 1:
		n += 1 << i
for i in range(40)[::-1]:
	(b, c) = (t >> i & 1, u >> i & 1)
	if b == 1 and c == 0:
		if n + (1 << i) <= a:
			n += 1 << i
if n > a or n == 0:
	print(-1)
else:
	print(a - n)


def solve(ls):
	import math
	(x, y, *ls) = ls
	z = x + y
	s = 0
	for a in ls:
		s ^= a
	if z - s < 0 or (z - s) % 2 == 1:
		return -1
	t = (z - s) // 2
	s_t = s & t
	if s_t > 0 or t > x:
		return -1
	a = t
	b = t
	first_set = math.floor(math.log2(s + 1))
	for i in range(first_set + 1)[::-1]:
		k = 1 << i
		if s & k:
			if a | k <= x:
				a = a | k
			else:
				b = b | k
	if a == 0:
		return -1
	return x - a

def main(istr, ostr):
	n = int(istr.readline().strip())
	ls = list(map(int, istr.readline().strip().split()))
	result = solve(ls)
	print(result, file=ostr)

def __starting_point():
	import sys
	main(sys.stdin, sys.stdout)
__starting_point()


import sys
N = int(input())
A = list(map(int, input().split()))
ALL = 0
for a in A:
	ALL ^= a
if ALL == 0:
	print(0)
	sys.exit()
ALL ^= A[0] ^ A[1]
K = A[0] + A[1]
L = []
for i in range(40, -1, -1):
	if 1 << i & ALL:
		L.append(1)
		K -= 1 << i
	elif K >= 2 * (1 << i):
		L.append(2)
		K -= 1 << i + 1
	else:
		L.append(0)
if K != 0:
	print(-1)
	sys.exit()
ans = 0
for i in range(41):
	if L[i] == 2:
		ans += 1 << 40 - i
if ans >= A[0]:
	print(-1)
	sys.exit()
for i in range(41):
	if L[i] == 1:
		if ans + (1 << 40 - i) < A[0]:
			ans += 1 << 40 - i
if ans == 0:
	print(-1)
	sys.exit()
print(A[0] - ans)


n = int(input())
l = list(map(int, input().split()))
x = 0
s = l[0] + l[1]
for i in l[2:]:
	x ^= i
if x > s or (s - x) % 2 or (s - x) // 2 & x:
	print(-1)
	exit()
a = (s - x) // 2
if a > l[0]:
	print(-1)
	exit()
for i in range(50, -1, -1):
	if 1 << i & x:
		if a + (1 << i) <= l[0]:
			a += 1 << i
if a == 0:
	print(-1)
else:
	print(l[0] - a)


n = int(input())
a = list(map(int, input().split()))
xor = 0
if n == 2:
	(a, b) = a
	if a >= b and (a + b) % 2 == 0:
		print((a + b) // 2 - b)
	else:
		print(-1)
	exit()
for i in range(2, n):
	xor ^= a[i]
(a, b) = (a[0], a[1])
sm = a + b
ls = []
smt = 0
for i in range(50)[::-1]:
	if xor & 1 << i:
		ls.append(1)
		smt += 1 << i
	elif smt + (2 << i) > sm:
		ls.append(0)
	else:
		ls.append(2)
		smt += 2 << i
if smt != sm:
	print(-1)
	exit()
mn = 0
mx = 0
for i in range(50):
	if ls[49 - i] == 1:
		mx += 1 << i
	elif ls[49 - i] == 2:
		mn += 1 << i
		mx += 1 << i
if not mn <= a:
	print(-1)
	exit()
ans = mn
for i in range(50):
	if ls[i] == 1:
		if ans + (1 << 49 - i) > a:
			continue
		else:
			ans += 1 << 49 - i
if ans == 0:
	print(-1)
else:
	print(a - ans)


from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))
tmp = 0
for a in A[2:]:
	tmp ^= a
INF = 10 ** 18

@lru_cache(None)
def F(a, b, xor):
	if a & 1 ^ b & 1 != xor & 1:
		return INF
	if xor == 0:
		return INF if a < b else (a - b) // 2
	x = 2 * F(a // 2, b // 2, xor // 2)
	y = 2 * F((a - 1) // 2, (b + 1) // 2, xor // 2) + 1
	x = min(x, y)
	if x >= INF:
		x = INF
	return x
x = F(A[0], A[1], tmp)
if x >= A[0]:
	x = -1
print(x)


import sys
sys.setrecursionlimit(10 ** 6)
K = 43

def main(input, print):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = a[0]
	a2 = a[1]
	s = a1 + a2
	x = 0
	for i in range(2, n):
		x ^= a[i]
	dp = [[[-1 for _ in range(2)] for _ in range(2)] for _ in range(K)]
	dp[0][0][0] = 0
	v = 1
	for i in range(K - 1):
		cx = x & 1
		cs = s & 1
		ca = a1 & 1
		for j in range(2):
			for k in range(2):
				if dp[i][j][k] == -1:
					continue
				for na in range(2):
					for nb in range(2):
						ni = i + 1
						nj = 0
						nk = k
						if na ^ nb != cx:
							continue
						ns = na + nb + j
						if ns % 2 != cs:
							continue
						if ns >= 2:
							nj = 1
						if ca < na:
							nk = 1
						elif ca == na:
							nk = k
						else:
							nk = 0
						dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k] | v * na)
		x >>= 1
		s >>= 1
		a1 >>= 1
		v <<= 1
	ans = dp[K - 1][0][0]
	if ans == -1 or ans == 0:
		print(-1)
	else:
		print(a[0] - ans)
main(sys.stdin.readline, print)


import sys
sys.setrecursionlimit(10 ** 7)
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right
from collections import deque
from collections import Counter
from itertools import accumulate, combinations, permutations
from heapq import heapify, heappop, heappush
from functools import lru_cache
from decimal import Decimal

def input():
	x = sys.stdin.readline()
	return x[:-1] if x[-1] == '\n' else x

def printl(li):
	_ = print(*li, sep='\n') if li else None

def argsort(s, return_sorted=False):
	inds = sorted(range(len(s)), key=lambda k: s[k])
	if return_sorted:
		return (inds, [s[i] for i in inds])
	return inds

def alp2num(c, cap=False):
	return ord(c) - 97 if not cap else ord(c) - 65

def num2alp(i, cap=False):
	return chr(i + 97) if not cap else chr(i + 65)

def matmat(A, B):
	(K, N, M) = (len(B), len(A), len(B[0]))
	return [[sum([A[i][k] * B[k][j] for k in range(K)]) for j in range(M)] for i in range(N)]

def matvec(M, v):
	(N, size) = (len(v), len(M))
	return [sum([M[i][j] * v[j] for j in range(N)]) for i in range(size)]

def T(M):
	(n, m) = (len(M), len(M[0]))
	return [[M[j][i] for j in range(n)] for i in range(m)]

def main():
	mod = 1000000007
	N = int(input())
	A = tuple(map(int, input().split()))
	ref = 0
	for i in range(2, N):
		ref ^= A[i]
	a0 = A[0]
	a1 = A[1]
	s = a0 + a1
	dp = [[[-1] * 2 for _ in range(2)] for _ in range(43)]
	refi = ref
	si = s
	dp[0][0][0] = 0
	shift = 1
	a = a0
	for i in range(42):
		ni = i + 1
		for j in range(2):
			for k in range(2):
				cur = dp[i][j][k]
				if cur == -1:
					continue
				for ai in range(0, 2):
					bi = refi & 1 ^ ai
					if bi + j + ai & 1 != si & 1:
						continue
					if ai > a & 1:
						nk = 1
					elif ai == a & 1:
						nk = k
					else:
						nk = 0
					nj = 0
					if bi + j + ai > 1:
						nj = 1
					dp[ni][nj][nk] = max(dp[ni][nj][nk], cur | shift * ai)
		refi = refi >> 1
		si >>= 1
		a >>= 1
		shift <<= 1
	x = dp[-1][0][0]
	if x == -1 or x == 0:
		print(-1)
	else:
		print(a0 - x)

def __starting_point():
	main()
__starting_point()


def main():
	n = int(input())
	A = list(map(int, input().split()))
	x = A[0] ^ A[1]
	for i in A:
		x ^= i
	s = A[0] + A[1]
	dp = [[[-1] * 2 for _ in range(2)] for _ in range(43)]
	dp[0][0][0] = 0
	v = 1
	a = A[0]
	for i in range(42):
		(cx, ca, cs) = (x & 1, a & 1, s & 1)
		for j in range(2):
			for k in range(2):
				if dp[i][j][k] == -1:
					continue
				for na in range(2):
					for nb in range(2):
						if na ^ nb != cx:
							continue
						(ni, nj, nk, ns) = (i + 1, 0, k, na + nb + j)
						if ns % 2 != cs:
							continue
						if ns >= 2:
							nj = 1
						if ca < na:
							nk = 1
						elif ca == na:
							nk = k
						else:
							nk = 0
						dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k] | v * na)
		x >>= 1
		s >>= 1
		a >>= 1
		v <<= 1
	a = dp[42][0][0]
	if a == 0 or a == -1:
		ans = -1
	else:
		ans = A[0] - a
	print(ans)
main()


from functools import reduce, lru_cache
INF = float('inf')
(N, a, b, *A) = map(int, open(0).read().split())
c = reduce(lambda a, b: a ^ b, A, 0)

@lru_cache(None)
def solve(a, b, c):
	if a % 2 ^ b % 2 != c % 2:
		return INF
	if c == 0:
		return INF if a < b else (a - b) // 2
	return min(2 * solve(a // 2, b // 2, c // 2), 1 + 2 * solve((a - 1) // 2, (b + 1) // 2, c // 2))
print(-1 if (res := solve(a, b, c)) >= a else res)


def digit(x):
	ret = 0
	while x > 0:
		x //= 2
		ret += 1
	return ret

def main():
	N = int(input())
	A = list(map(int, input().split()))
	g = 0
	for i in range(2, N):
		g ^= A[i]
	a0 = A[0]
	a1 = A[1]
	ans = 0
	half = 2 ** 20
	if a0 < half:
		for i in range(a0):
			t0 = a0 - i
			t1 = a1 + i
			if t0 ^ t1 == g:
				print(i)
				return
		print(-1)
		return
	ug = g >> 20
	b0 = a0 >> 20
	b1 = a1 >> 20
	upper_ans_0 = -1
	for i in range(b0):
		t0 = b0 - i
		t1 = b1 + i
		if t0 ^ t1 == ug:
			upper_ans_0 = i
			break
	upper_ans_1 = -1
	for i in range(b0):
		t0 = b0 - i
		t1 = b1 + 1 + i
		if t0 ^ t1 == ug:
			upper_ans_1 = i
			break
	upper_ans_2 = -1
	for i in range(b0 - 1):
		t0 = b0 - 1 - i
		t1 = b1 + i
		if t0 ^ t1 == ug:
			upper_ans_2 = i
			break
	upper_ans_3 = -1
	for i in range(b0 - 1):
		t0 = b0 - 1 - i
		t1 = b1 + 1 + i
		if t0 ^ t1 == ug:
			upper_ans_3 = i
			break
	lower_answers = []
	for i in range(half):
		t0 = (a0 - i) % half
		t1 = (a1 + i) % half
		if t0 ^ t1 == g % half:
			lower_answers.append(i)
	if len(lower_answers) == 0:
		print(-1)
		return
	answers = []
	for l in lower_answers:
		if a0 % half >= l:
			if a1 % half + l < half:
				if upper_ans_0 != -1:
					answers.append((upper_ans_0 << 20) + l)
			elif upper_ans_1 != -1:
				answers.append((upper_ans_1 << 20) + l)
		elif a1 % half + l < half:
			if upper_ans_2 != -1:
				answers.append((upper_ans_2 << 20) + l)
		elif upper_ans_3 != -1:
			answers.append((upper_ans_3 << 20) + l)
	if len(answers) == 0:
		print(-1)
		return
	answers.sort()
	print(answers[0])
main()


from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():

	def dp(a, b, s):
		if mem[a, b, s] is not None:
			return mem[a, b, s]
		x = a & 1
		y = b & 1
		z = s & 1
		if x ^ y != z:
			return float('inf')
		res = 2 * dp(a >> 1, b >> 1, s >> 1)
		if a > 1:
			nr = 2 * dp(a - 1 >> 1, b + 1 >> 1, s >> 1) + 1
			if nr < res:
				res = nr
		mem[a, b, s] = res
		return res
	n = I()
	a = LI()
	s = 0
	for i in a[2:]:
		s ^= i
	b = a[1]
	a = a[0]
	mem = defaultdict(lambda : None)
	mem[0, 0, 0] = 0
	ans = dp(a, b, s)
	if ans == float('inf'):
		ans = -1
	print(ans)
	return
solve()


n = int(input())
a = list(map(int, input().split()))
x = 0
for i in range(2, n):
	x ^= a[i]
s = a[0] + a[1]
if s < x or (s - x) % 2 == 1:
	print(-1)
	exit()
d = (s - x) // 2
if d & x != 0 or d > a[0]:
	print(-1)
	exit()
i = 50
ans = d
while i >= 0:
	if x >> i & 1:
		if (1 << i) + ans <= a[0]:
			ans += 1 << i
	i -= 1
if ans == 0:
	print(-1)
	exit()
print(a[0] - ans)


n = int(input())
A = [int(i) for i in input().split()]
A1 = A[0]
A2 = A[1]
c = 0
for ele in A[2:]:
	c ^= ele
d = A1 + A2 - c
if d % 2 == 1:
	print(-1)
else:
	d = d // 2
	flgs = []
	for i in range(41):
		fand = d & 1 << i
		fxor = c & 1 << i
		if fand & fxor:
			print(-1)
			break
		elif fand:
			flgs.append(1)
		elif fxor:
			flgs.append(2)
		else:
			flgs.append(0)
	else:
		flgs = flgs[::-1]
		ans = 0
		for i in range(len(flgs)):
			if flgs[i] == 1:
				ans += 2 ** (41 - i - 1)
		if ans > A1:
			print(-1)
		else:
			for i in range(len(flgs)):
				if flgs[i] == 2:
					if ans + 2 ** (41 - i - 1) <= A1:
						ans += 2 ** (41 - i - 1)
			if ans == 0:
				print(-1)
			else:
				print(A1 - ans)


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()))
val = 0
for num in a[2:]:
	val ^= num
k = a[0] + a[1]
if (k - val) % 2 != 0 or k < val:
	ans = -1
else:
	tmp = (k - val) // 2
	if tmp < 0 or 2 * tmp > k:
		ans = -1
	else:
		v1 = tmp
		v2 = tmp
		kouho = []
		ans = None
		if tmp > a[0]:
			ans = -1
		diff = k - 2 * tmp
		for i in range(diff.bit_length()):
			if diff & 1 << i & tmp:
				ans = -1
				break
			elif diff & 1 << i:
				kouho.append(1 << i)
		s = sum(kouho)
		if ans is None:
			for num in kouho[::-1]:
				s -= num
				if v2 + s < a[1]:
					v2 += num
				elif v1 + num <= a[0]:
					v1 += num
				else:
					v2 += num
			if v1 == 0:
				ans = -1
			else:
				ans = a[0] - v1
		else:
			ans = -1
print(ans)


(N,) = map(int, input().split())
X = list(map(int, input().split()))
t = 0
for x in X:
	t = t ^ x
inf = float('inf')
d = dict()

def it(x, y, z):
	if (x, y, z) in d:
		return d[x, y, z]
	(xm, ym, zm) = (x % 2, y % 2, z % 2)
	if xm ^ ym != zm:
		d[x, y, z] = inf
		return inf
	if x ^ y == z:
		d[x, y, z] = 0
		return 0
	Rz = 2 * it(x >> 1, y >> 1, z >> 1)
	Ro = inf
	if x:
		Ro = 2 * it(x - 1 >> 1, y + 1 >> 1, z >> 1) + 1
	Rz = min(Rz, Ro)
	d[x, y, z] = Rz
	return Rz
r = it(X[0], X[1], t ^ X[0] ^ X[1])
if 0 <= r < X[0]:
	print(r)
else:
	print(-1)


n = int(input())
(a, b, *L) = map(int, input().split())
x = 0
for l in L:
	x ^= l
s = a + b
if s - x < 0 or (s - x) % 2:
	print(-1)
	exit()
d = (s - x) // 2
if d & x:
	print(-1)
	exit()
if d > a:
	print(-1)
	exit()
for i in range(50, -1, -1):
	if x >> i & 1 and d | 1 << i <= a:
		d |= 1 << i
if d == 0:
	print(-1)
	exit()
ans = a - d
print(ans)


N = int(input())
A = list(map(int, input().split()))
(a, b) = (A[0], A[1])
x = 0
for i in range(2, N):
	x ^= A[i]
s = a + b
M = 42
dp = [[[-1] * 2 for _ in range(2)] for _ in range(M + 1)]
dp[0][0][0] = 0
v = 1
for i in range(M):
	cs = s & 1
	cx = x & 1
	ca = a & 1
	for j in range(2):
		for k in range(2):
			if dp[i][j][k] == -1:
				continue
			for na in range(2):
				for nb in range(2):
					if na ^ nb != cx:
						continue
					ns = na + nb + j
					if ns & 1 != cs:
						continue
					ni = i + 1
					nj = 1 if ns >= 2 else 0
					if na > ca:
						nk = 1
					elif na < ca:
						nk = 0
					else:
						nk = k
					dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k] + na * v)
	s >>= 1
	x >>= 1
	a >>= 1
	v <<= 1
amax = dp[M][0][0]
if amax <= 0:
	print(-1)
else:
	print(A[0] - amax)


n = int(input())
a = list(map(int, input().split()))
S = a[0] + a[1]
C = 0
for i in range(2, n):
	C ^= a[i]
D = S - C
if D < 0 or D % 2 == 1:
	print(-1)
	exit()
D //= 2
ans = 0
free_keta = []
for i in range(100):
	if C & 1 << i != 0:
		free_keta.append(i)
		if D & 1 << i != 0:
			print(-1)
			exit()
	else:
		ans += D & 1 << i
if ans > a[0]:
	print(-1)
	exit()
for keta in free_keta[::-1]:
	if ans + (1 << keta) <= a[0]:
		ans += 1 << keta
if ans == 0:
	print(-1)
	exit()
print(a[0] - ans)


n = int(input())
A = list(map(int, input().split()))
a = A[0]
b = A[1]
x = 0
for i in A[2:]:
	x ^= i
d = {}

def F(a, b, xor):
	if (a, b, xor) in d:
		return d[a, b, xor]
	if a & 1 ^ b & 1 != xor & 1:
		return float('INF')
	if xor == 0:
		if a < b:
			return float('INF')
		else:
			return (a - b) // 2
	c1 = 2 * F(a // 2, b // 2, xor // 2)
	c2 = 2 * F((a - 1) // 2, (b + 1) // 2, xor // 2) + 1
	f = min(c1, c2)
	d[a, b, xor] = f
	return f
ans = F(a, b, x)
if ans >= a:
	print(-1)
else:
	print(ans)


import pprint
N = int(input())
A = list(map(int, input().split()))
bitlen = 42
flag = 1
exor = 0
andsum = 0
ex = [0] * bitlen
an = [0] * bitlen
num = 0
for i in range(2, N):
	exor = exor ^ A[i]
andsum = A[0] + A[1] - exor
if andsum % 2 != 0 or andsum < 0:
	flag = 0
else:
	andsum = andsum // 2
	for i in range(bitlen):
		if exor >> i & 1:
			ex[i] = 1
		if andsum >> i & 1:
			an[i] = 1
	num = andsum
	for i in range(bitlen):
		if an[i] == 1 and ex[i] == 1:
			flag = 0
			break
	if num > A[0]:
		flag = 0
	for i in range(bitlen - 1, -1, -1):
		if ex[i] == 1:
			if num + pow(2, i) <= A[0]:
				num = num + pow(2, i)
	if num == 0:
		flag = 0
if flag == 0:
	print(-1)
else:
	print(A[0] - num)


import random
N = int(input())
A = list(map(int, input().split()))
S = A[0] + A[1]
X = 0
for a in A[2:]:
	X ^= a
D = S - X >> 1
if S != X + (D << 1) or D > A[0] or X & D != 0:
	print(-1)
	return
a = D
b = 2 ** 64
while b > 0:
	if X & b != 0 and a | b <= A[0]:
		a |= b
	b >>= 1
if a == 0:
	print(-1)
	return
print(A[0] - a)


N = int(input())
A = list(map(int, input().split()))
XOR = 0
for a in A[2:]:
	XOR ^= a
S = A[0] + A[1]
DP = [[[1 << 60] * 2 for i in range(2)] for j in range(60)]
DP[0][0][1] = 0
for i in range(59):
	CX = 0
	if XOR & 1 << i != 0:
		CX = 1
	CS = 0
	if S & 1 << i != 0:
		CS = 1
	CA = 0
	if A[1] & 1 << i != 0:
		CA = 1
	for j in range(2):
		for k in range(2):
			if DP[i][j][k] == 1 << 60:
				continue
			for (na, nb) in [(0, 0), (0, 1), (1, 0), (1, 1)]:
				if na ^ nb != CX:
					continue
				if (na + nb + j) % 2 != CS:
					continue
				if na + nb + j >= 2:
					nj = 1
				else:
					nj = 0
				if CA < nb:
					nk = 1
				elif CA == nb:
					nk = k
				else:
					nk = 0
				DP[i + 1][nj][nk] = min(DP[i + 1][nj][nk], DP[i][j][k] | (1 << i) * nb)
ANS = DP[59][0][1] - A[1]
if ANS >= A[0]:
	print(-1)
else:
	print(ANS)


N = int(input())
A = list(map(int, input().split()))
P = 41
X = 0
for i in range(2, N):
	X ^= A[i]
S = A[0] + A[1]
A1 = A[0]
(D, M) = divmod(S - X, 2)
ans = -1
if M % 2 == 0 and D & X == 0 and (D <= A1):
	Y = 0
	for p in range(P, -1, -1):
		if X >> p & 1 == 1:
			new_Y = Y ^ 1 << p
			if D ^ new_Y <= A1:
				Y = new_Y
	ans = A1 - (D ^ Y)
	if ans == A1:
		ans = -1
print(ans)


n = int(input())
alst = list(map(int, input().split()))
if n == 2:
	if sum(alst) % 2 != 0:
		print(-1)
	elif alst[0] < alst[1]:
		print(-1)
	else:
		print((alst[0] - alst[1]) // 2)
	exit()
if alst.count(1) == n:
	if n % 2 == 0:
		print(0)
	else:
		print(-1)
	exit()
if alst.count(1) == n - 1:
	print(-1)
	exit()
xor = 0
for num in alst[2:]:
	xor ^= num
total = alst[0] + alst[1]
if xor > total:
	print(-1)
	exit()
diff = total - xor
if diff % 2 == 1:
	print(-1)
	exit()
if alst[0] == 1:
	if xor == alst[0] ^ alst[1]:
		print(0)
	else:
		print(-1)
	exit()
diff //= 2
total_bin = format(total, 'b')
diff_bin = format(diff, 'b')
xor_bin = format(xor, 'b')
i = len(total_bin)
ans = 0
for j in range(i, 0, -1):
	if j <= len(diff_bin):
		if diff_bin[-j] == '1':
			ans += 2 ** (j - 1)
			continue
for j in range(i, 0, -1):
	if j <= len(diff_bin):
		if diff_bin[-j] == '1':
			continue
	if j <= len(xor_bin):
		if xor_bin[-j] == '0':
			continue
	if ans + 2 ** (j - 1) < alst[0]:
		ans += 2 ** (j - 1)
if ans ^ total - ans != xor:
	print(-1)
elif ans == 0 or ans >= alst[0]:
	print(-1)
else:
	print(alst[0] - ans)


n = int(input())
a = list(map(int, input().split()))
c = 0
for i in range(2, n):
	c = c ^ a[i]
start = a[0]
(a, b) = (a[0], a[1])
if a ^ b == c:
	print(0)
	exit()
dif = a + b - c
if dif % 2 == 1:
	print(-1)
	exit()
dif = dif // 2
for i in range(40):
	if c >> i & 1 & (dif >> i & 1):
		print(-1)
		exit()
if dif > start:
	print(-1)
	exit()
goal = dif
for i in range(40, -1, -1):
	if c >> i & 1:
		if goal + 2 ** i <= start:
			goal += 2 ** i
if goal == 0:
	print(-1)
	exit()
print(start - goal)


from functools import lru_cache
import sys
input = sys.stdin.readline

@lru_cache(maxsize=None)
def dfs(a, b, c):
	if (a ^ b) & 1 != c & 1:
		return float('inf')
	if a == 0:
		return 0 if b == c else float('inf')
	return min(2 * dfs(a >> 1, b >> 1, c >> 1), 2 * dfs(a - 1 >> 1, b + 1 >> 1, c >> 1) + 1)
N = int(input())
A = list(map(int, input().split()))
B = 0
for i in range(2, N):
	B ^= A[i]
ans = dfs(A[0], A[1], B)
print(ans if ans < float('inf') and A[0] > ans else -1)


N = int(input())
A = [int(i) for i in input().split()]
S = A[0] + A[1]
X = 0
for i in range(2, N):
	X ^= A[i]
dp = [[[-1] * 2 for _ in range(2)] for _ in range(60)]
dp[0][0][0] = 0
for i in range(59):
	cs = S >> i & 1
	cx = X >> i & 1
	ca = A[0] >> i & 1
	for j in (0, 1):
		for k in (0, 1):
			if dp[i][j][k] < 0:
				continue
			for na in (0, 1):
				for nb in (0, 1):
					ni = i + 1
					nj = 0
					nk = k
					if na ^ nb != cx:
						continue
					ns = na + nb + j
					if ns % 2 != cs:
						continue
					if ns >= 2:
						nj = 1
					if ca < na:
						nk = 1
					elif ca == na:
						nk = k
					else:
						nk = 0
					dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k] | na << i)
if 1 <= dp[-1][0][0] <= A[0]:
	print(A[0] - dp[-1][0][0])
else:
	print(-1)


def compute(S, X):
	if (S - X) % 2 == 1:
		print(-1)
		return
	A = (S - X) // 2
	a = 0
	ambiguous = [0] * 64
	for i in range(63, -1, -1):
		Xi = X & 1 << i
		Ai = A & 1 << i
		if Xi == 0 and Ai == 0:
			pass
		elif Xi == 0 and Ai > 0:
			a = 1 << i | a
		elif Xi > 0 and Ai == 0:
			ambiguous[i] = 1
		else:
			print(-1)
			return
	for i in range(63, -1, -1):
		if ambiguous[i] == 1:
			R = 1 << i | a
			if R <= a1[0]:
				a = R
			else:
				a = 0 << i | a
	if a > a1[0]:
		print(-1)
	elif a == 0 and a1[0] != 0:
		print(-1)
	else:
		print(a1[0] - a)
import sys
n = int(input())
a1 = list(map(int, input().split()))
nimsum = 0
for i in range(2, n):
	nimsum = a1[i] ^ nimsum
compute(a1[0] + a1[1], nimsum)


N = list(map(int, input().split()))
As = list(map(int, input().split()))
added = As[0] + As[1]
xored = 0
for A in As[2:]:
	xored ^= A
anded = added - xored
if anded % 2 == 1:
	print(-1)
	return
else:
	anded >>= 1
left_stones_l_A0 = ''
left_stones_e_A0 = ''
for (i, (a, x)) in enumerate(zip(format(anded, '045b'), format(xored, '045b'))):
	if x == '0':
		if a == '0':
			left_stones_l_A0 += '0'
			left_stones_e_A0 += '0'
		else:
			left_stones_l_A0 += '1'
			left_stones_e_A0 += '1'
	elif a == '0':
		if int(left_stones_l_A0 + '1' + '1' * (44 - i), base=2) <= As[0]:
			left_stones_l_A0 += '1'
		else:
			left_stones_l_A0 += '0'
		if int(left_stones_e_A0 + '1' + '1' * (44 - i), base=2) <= As[0]:
			left_stones_e_A0 += '1'
			left_stones_l_A0 = left_stones_e_A0
		elif int(left_stones_e_A0 + '1' + '0' * (44 - i), base=2) <= As[0]:
			left_stones_l_A0 = left_stones_e_A0 + '0'
			left_stones_e_A0 += '1'
		elif int(left_stones_e_A0 + '0' + '0' * (44 - i), base=2) <= As[0]:
			left_stones_e_A0 += '0'
		else:
			left_stones_e_A0 = left_stones_l_A0
	else:
		print(-1)
		return
if int(left_stones_e_A0, base=2) <= As[0]:
	ans = As[0] - int(left_stones_e_A0, base=2)
else:
	ans = As[0] - int(left_stones_l_A0, base=2)
if 0 <= ans < As[0]:
	print(ans)
else:
	print(-1)


import sys
n = int(input())
a = [int(x) for x in input().split()]
T = 0
for i in range(2, n):
	T ^= a[i]
S = a[0] + a[1]
D = (S - T) // 2
if S < T or (S - T) % 2 or D & T:
	print(-1)
	sys.exit()
for i in range(T.bit_length() + 1, -1, -1):
	if T & 1 << i | D <= a[0]:
		D |= T & 1 << i
if 0 < D <= a[0]:
	print(a[0] - D)
else:
	print(-1)


N = int(input())
(A, B, *C) = list(map(int, input().split()))
X = 0
for c in C:
	X ^= c
S = A + B
K = 43
dp = [[[-1] * 2 for _ in range(2)] for _ in range(K)]
dp[0][0][0] = 0
for i in range(K - 1):
	cx = X >> i & 1
	cs = S >> i & 1
	ca = A >> i & 1
	for j in range(2):
		for k in range(2):
			if dp[i][j][k] == -1:
				continue
			for na in range(2):
				for nb in range(2):
					if na ^ nb != cx:
						continue
					ns = na + nb + j
					if ns % 2 != cs:
						continue
					nj = ns // 2
					if ca < na:
						nk = 1
					elif ca == na:
						nk = k
					else:
						nk = 0
					dp[i + 1][nj][nk] = max(dp[i + 1][nj][nk], dp[i][j][k] + 2 ** i * na)
a = dp[-1][0][0]
if a == 0 or a == -1:
	print(-1)
else:
	print(A - a)


N = int(input())
A = list(map(int, input().split()))
xor = 0
for a in A[2:]:
	xor ^= a
n = A[0] + A[1] - xor
if n < 0 or n % 2:
	print(-1)
	quit()
n //= 2
a = b = 0
digit = 1
d = []
while n or xor:
	n0 = n & 1
	xor0 = xor & 1
	if n0:
		if xor0:
			print(-1)
			quit()
		else:
			a += digit
			b += digit
	elif xor0:
		b += digit
		d.append(digit)
	digit *= 2
	n >>= 1
	xor >>= 1
if a > A[0]:
	print(-1)
	quit()
while d:
	dd = d.pop()
	if a + dd <= A[0]:
		a += dd
		b -= dd
if a:
	print(A[0] - a)
else:
	print(-1)


import sys

def solve(n, aaa):
	if n == 2:
		(h, m) = divmod(sum(aaa), 2)
		if m == 1 or h > aaa[0]:
			return -1
		return aaa[0] - h
	x = 0
	for a in aaa[2:]:
		x ^= a
	(a0, a1) = aaa[:2]
	s = a0 + a1
	if s & 1 != x & 1:
		return -1
	(p, q) = (0, 0)
	b = 1 << 40
	swappable = []
	while b:
		bx = x & b
		if bx == 0:
			if s >= 2 * b:
				if p | b <= a0:
					p |= b
					q |= b
					s -= 2 * b
				elif swappable:
					bs = swappable.pop()
					p ^= bs
					q ^= bs
					p |= b
					q |= b
					s -= 2 * b
				else:
					return -1
		else:
			if s < b:
				return -1
			if p | b <= a0 and q | b > a1:
				p |= b
				swappable.append(b)
			else:
				q |= b
			s -= b
		b >>= 1
	if p == 0:
		return -1
	assert s == 0
	assert p ^ q == x
	assert a0 - p == q - a1
	return a0 - p
(n, *aaa) = map(int, sys.stdin.buffer.read().split())
print(solve(n, aaa))


import sys
input = sys.stdin.readline
import math
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
MOD = 10 ** 9 + 7
INF = float('inf')
AZ = 'abcdefghijklmnopqrstuvwxyz'

def I():
	return int(input().strip())

def S():
	return input().strip()

def IL():
	return list(map(int, input().split()))

def SL():
	return list(map(str, input().split()))

def ILs(n):
	return list((int(input()) for _ in range(n)))

def SLs(n):
	return list((input().strip() for _ in range(n)))

def ILL(n):
	return [list(map(int, input().split())) for _ in range(n)]

def SLL(n):
	return [list(map(str, input().split())) for _ in range(n)]

def P(arg):
	print(arg)
	return

def Y():
	print('Yes')
	return

def N():
	print('No')
	return

def E():
	exit()

def PE(arg):
	print(arg)
	exit()

def YE():
	print('Yes')
	exit()

def NE():
	print('No')
	exit()

def DD(arg):
	return defaultdict(arg)

def inv(n):
	return pow(n, MOD - 2, MOD)
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

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 make_primes(N):
	max = int(math.sqrt(N))
	seachList = [i for i in range(2, N + 1)]
	primeNum = []
	while seachList[0] <= max:
		primeNum.append(seachList[0])
		tmp = seachList[0]
		seachList = [i for i in seachList if i % tmp != 0]
	primeNum.extend(seachList)
	return primeNum

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)

def count_bit(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count

def base_10_to_n(X, n):
	if X // n:
		return base_10_to_n(X // n, n) + [X % n]
	return [X % n]

def base_n_to_10(X, n):
	return sum((int(str(X)[-i - 1]) * n ** i for i in range(len(str(X)))))

def base_10_to_n_without_0(X, n):
	X -= 1
	if X // n:
		return base_10_to_n_without_0(X // n, n) + [X % n]
	return [X % n]

def int_log(n, a):
	count = 0
	while n >= a:
		n //= a
		count += 1
	return count
N = I()
A = IL()
B = 0
if N >= 3:
	for a in A[2:]:
		B ^= a
S = A[0] + A[1]
if (S - B) % 2:
	print(-1)
	exit()
D = (S - B) // 2
if D & B or D > A[0]:
	print(-1)
	exit()
ans = D
for i in range(50)[::-1]:
	if ans + (B & 1 << i) < A[0]:
		ans += B & 1 << i
ans = A[0] - ans if ans else -1
print(ans)


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	n = II()
	aa = LI()
	x = 0
	for a in aa[2:]:
		x ^= a
	t = aa[0] + aa[1] - x
	if t < 0 or t & 1:
		print(-1)
		return
	t >>= 1
	a0 = a1 = 0
	for i in range(40, -1, -1):
		dt = t >> i & 1
		dx = x >> i & 1
		if (dt, dx) == (1, 1):
			print(-1)
			return
		if (dt, dx) == (1, 0):
			a0 |= 1 << i
			a1 |= 1 << i
	for i in range(40, -1, -1):
		dt = t >> i & 1
		dx = x >> i & 1
		if (dt, dx) == (0, 1):
			if a0 | 1 << i <= aa[0]:
				a0 |= 1 << i
			else:
				a1 |= 1 << i
	if a0 > 0 and a0 <= aa[0]:
		print(aa[0] - a0)
	else:
		print(-1)
main()


import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
xsm = 0
sm = a[0] + a[1]
for i in range(2, N):
	xsm ^= a[i]
t = sm - xsm
table = [0] * 41
for i in range(40, -1, -1):
	if t >= 1 << i + 1:
		t -= 1 << i + 1
		table[i] = 1
if t:
	print(-1)
	exit(0)
t = a[0]
res = 0
for i in range(40, -1, -1):
	if t >= 1 << i:
		if table[i]:
			t -= 1 << i
			res += 1 << i
for i in range(40, -1, -1):
	if t >= 1 << i:
		if xsm & 1 << i:
			t -= 1 << i
			res += 1 << i
if res == 0 or res ^ sm - res != xsm:
	print(-1)
else:
	print(a[0] - res)


import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
YesNo = lambda b: bool([print('Yes')] if b else print('No'))
YESNO = lambda b: bool([print('YES')] if b else print('NO'))
int1 = lambda x: int(x) - 1
N = input()
A = tuple(map(int, input().split()))
X = 0
for x in A[2:]:
	X ^= x
S = A[0] + A[1]
if (S - X) % 2:
	print(-1)
	exit()
D = (S - X) // 2
ans = 0
tmp = 0
ttmp = 0
f = False
for i in range(50):
	if D >> i & 1 == X >> i & 1 == 1:
		print(-1)
		exit()
	elif D >> i & 1 == 1 and X >> i & 1 == 0:
		if A[0] >> i & 1 == 0:
			ans -= 1 << i
			f = True
	elif D >> i & 1 == 0 and X >> i & 1 == 1:
		if A[0] >> i & 1 == 1 and f:
			tmp = 1 << i
			ans += ttmp
			ttmp = 0
			f = False
		elif A[0] >> i & 1 == 0:
			ttmp -= 1 << i
	elif A[0] >> i & 1 == 1:
		ans += 1 << i
		tmp = 0
		ans += ttmp
		ttmp = 0
		f = False
if f:
	print(-1)
elif ans + tmp >= A[0]:
	print(-1)
else:
	print(ans + tmp)


N = int(input())
A = list(map(int, input().split()))
X = 0
for i in range(2, N):
	X ^= A[i]
if X > A[0] + A[1]:
	print(-1)
else:
	Y = A[0] + A[1] - X
	bY = bin(Y)[2:][::-1]
	bX = bin(X)[2:][::-1]
	if bY[0] == '1':
		print(-1)
	else:
		flag = True
		for i in range(1, len(bY)):
			if bY[i] == '1':
				if i - 1 < len(bX):
					if bX[i - 1] == '1':
						flag = False
						break
		if flag:
			if Y // 2 > A[0]:
				print(-1)
			else:
				a = Y // 2
				for i in range(len(bX)):
					if bX[len(bX) - i - 1] == '1':
						if a + 2 ** (len(bX) - i - 1) <= A[0]:
							a += 2 ** (len(bX) - i - 1)
				if a != 0:
					print(A[0] - a)
				else:
					print(-1)
		else:
			print(-1)


import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
S = A[0] + A[1]
X = 0
A0 = A[0]
for i in range(2, N):
	X ^= A[i]
L = 45
dp = [[[-1] * 2 for _ in range(2)] for _ in range(L + 1)]
dp[0][0][0] = 0
for i in range(L):
	for j in range(2):
		for k in range(2):
			if dp[i][j][k] == -1:
				continue
			for a in range(2):
				for b in range(2):
					(nj, s) = divmod(a + b + j, 2)
					x = a ^ b
					if s != S & 1:
						continue
					if x != X & 1:
						continue
					if a < A0 & 1:
						nk = 0
					elif a > A0 & 1:
						nk = 1
					else:
						nk = k
					dp[i + 1][nj][nk] = max(dp[i + 1][nj][nk], dp[i][j][k] + (a << i))
	S >>= 1
	X >>= 1
	A0 >>= 1
if dp[L][0][0] <= 0:
	print(-1)
else:
	print(A[0] - dp[L][0][0])


n = int(input())
a = list(map(int, input().split()))
if n == 2:
	if a[0] >= a[1] and (a[0] - a[1]) % 2 == 0:
		print((a[0] - a[1]) // 2)
	else:
		print(-1)
else:
	num = 0
	for i in range(2, n):
		num ^= a[i]
	_and = a[0] + a[1] - num
	if _and % 2 != 0 or a[0] < _and // 2 or _and // 2 & num != 0:
		print(-1)
	else:
		_and //= 2
		max_2 = 1
		while max_2 <= num:
			max_2 *= 2
		a0 = _and
		while max_2 >= 1:
			if num & max_2 != 0 and a0 + max_2 <= a[0]:
				a0 += max_2
			max_2 //= 2
		if a0 != 0:
			print(a[0] - a0)
		else:
			print(-1)


N = int(input())
A = list(map(int, input().split()))
X = 0
for i in range(2, N):
	X ^= A[i]
S = A[0] + A[1]
T = S - X
Y = 0
for i in range(41):
	if 1 << i + 1 & T:
		Y += 1 << i
if Y ^ S - Y ^ X:
	print(-1)
	exit()
for i in range(41, -1, -1):
	if X & 1 << i and Y + (1 << i) <= A[0]:
		Y += 1 << i
if 0 < Y <= A[0]:
	print(A[0] - Y)
else:
	print(-1)


from functools import lru_cache
(N,) = map(int, input().split())
X = list(map(int, input().split()))
t = 0
for x in X:
	t = t ^ x
inf = float('inf')

@lru_cache(None)
def it(x, y, z):
	(xm, ym, zm) = (x % 2, y % 2, z % 2)
	if xm ^ ym != zm:
		return inf
	if x ^ y == z:
		return 0
	Rz = 2 * it(x >> 1, y >> 1, z >> 1)
	Ro = inf
	if x:
		Ro = 2 * it(x - 1 >> 1, y + 1 >> 1, z >> 1) + 1
	Rz = min(Rz, Ro)
	return Rz
r = it(X[0], X[1], t ^ X[0] ^ X[1])
if 0 <= r < X[0]:
	print(r)
else:
	print(-1)


def main(n, a):
	s = a[0] + a[1]
	z = 0
	for ai in a[2:]:
		z ^= ai
	if s - z < 0 or (s - z) % 2 == 1:
		return -1
	d = (s - z) // 2
	if d & z != 0:
		return -1
	if not d <= a[0]:
		return -1
	part = []
	i = 0
	while z // pow(2, i):
		if z // pow(2, i) % 2 == 1:
			part.append(pow(2, i))
		i += 1
	ans = float('inf')
	k = len(part)
	x = 0
	while part:
		tmp = part.pop()
		if d ^ x + tmp <= a[0]:
			x += tmp
	return a[0] - (d ^ x) if d ^ x else -1
n = int(input())
a = list(map(int, input().split()))
print(main(n, a))


N = int(input())
A = list(map(int, input().split()))
xor = 0
for a in A[2:]:
	xor ^= a
n = A[0] + A[1] - xor
if n < 0 or n % 2:
	print(-1)
	return
n //= 2
a = b = 0
digit = [1]
d = []
count = 0
while n or xor:
	n0 = n & 1
	xor0 = xor & 1
	if n0:
		if xor0:
			print(-1)
			return
		else:
			a += digit[-1]
			b += digit[-1]
	elif xor0:
		b += digit[-1]
		d.append(count)
	digit.append(digit[-1] * 2)
	count += 1
	n >>= 1
	xor >>= 1
if a > A[0]:
	print(-1)
	return
while d:
	c = d.pop()
	if a + digit[c] <= A[0]:
		a += digit[c]
		b -= digit[c]
if a:
	print(A[0] - a)
else:
	print(-1)


import sys
from functools import lru_cache

def solve(n, aaa):
	if n == 2:
		(h, m) = divmod(sum(aaa), 2)
		if m == 1 or h > aaa[0]:
			return -1
		return aaa[0] - h
	x = 0
	for a in aaa[2:]:
		x ^= a
	(a0, a1) = aaa[:2]
	s = a0 + a1
	if s & 1 != x & 1:
		return -1
	b = 1 << 40
	MASK = (b << 1) - 1

	@lru_cache(maxsize=None)
	def dfs(p, b):
		if b == 0:
			return p
		m = (MASK ^ b - 1) << 1
		q = p ^ x & m
		if x & b == 0:
			if s >= p + q + 2 * b:
				if p | b <= a0:
					return dfs(p | b, b >> 1)
				else:
					return -1
			return dfs(p, b >> 1)
		else:
			if s < p + q + b:
				return -1
			if p | b <= a0:
				ret = dfs(p | b, b >> 1)
				if ret != -1:
					return ret
			return dfs(p, b >> 1)
	ret = dfs(0, b)
	if ret <= 0:
		return -1
	return a0 - ret
(n, *aaa) = map(int, sys.stdin.buffer.read().split())
print(solve(n, aaa))


N = int(input())
A = list(map(int, input().split()))
xorValue = 0
sumValue = A[0] + A[1]
for i in range(2, N):
	xorValue ^= A[i]
if sumValue % 2 != xorValue % 2:
	print(-1)
else:
	Base = (sumValue - xorValue) // 2
	if Base > A[0]:
		print(-1)
	else:
		strXOR = bin(xorValue)[2:]
		minStoneMovement = A[0] - Base
		strBase = bin(Base)[2:]
		lenStrXOR = len(strXOR)
		cannotMove = False
		if Base < 0:
			cannotMove = True
		for i in range(-1, -1 * min(len(strXOR), len(strBase)) - 1, -1):
			if strBase[i] == '1' and strXOR[i] == '1':
				cannotMove = True
				break
		if not cannotMove:
			for i in range(lenStrXOR):
				if strXOR[i] == '1' and minStoneMovement >= 2 ** (lenStrXOR - 1 - i):
					minStoneMovement -= 2 ** (lenStrXOR - 1 - i)
		if minStoneMovement == A[0] or cannotMove:
			print(-1)
		else:
			print(minStoneMovement)


from sys import exit
n = int(input())
a = list(map(int, input().split()))
X = 0
for i in range(2, n):
	X ^= a[i]
A = (a[0] + a[1] - X) // 2
if a[0] + a[1] - X != A * 2 or A > a[0] or A < 0 or X & A:
	print(-1)
	exit()
res = A
for i in range(42, -1, -1):
	if X >> i & 1:
		if res + (1 << i) <= a[0]:
			res += 1 << i
if res == 0:
	print(-1)
	exit()
print(a[0] - res)


N = int(input())
A = list((int(a) for a in input().split()))
a = A[0]
b = A[1]
S = a + b
X = 0
for i in range(2, N):
	X ^= A[i]
dp = [[[-1] * 2 for i in range(2)] for j in range(50)]
dp[0][0][0] = 0
for i in range(49):
	cur_s = S >> i & 1
	cur_x = X >> i & 1
	cur_a = a >> i & 1
	for (j, k) in ((0, 0), (0, 1), (1, 0), (1, 1)):
		if dp[i][j][k] == -1:
			continue
		for (p, q) in ((0, 0), (0, 1), (1, 0), (1, 1)):
			if p ^ q != cur_x:
				continue
			if p + q + j & 1 != cur_s:
				continue
			ni = i + 1
			nj = 0
			if p + q + j >= 2:
				nj = 1
			if cur_a < p:
				nk = 1
			elif cur_a > p:
				nk = 0
			else:
				nk = k
			dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k] | (1 << i) * p)
tmp = dp[49][0][0]
if tmp == 0 or tmp == -1:
	print(-1)
else:
	print(a - tmp)


N = int(input())
A = list(map(int, input().split()))
X = 0
if N > 2:
	X = A[2]
for i in range(3, N):
	X = (X | A[i]) - (X & A[i])
S = A[0] + A[1]
if (S - X) % 2 == 1 or S - X < 0:
	print(-1)
else:
	D = (S - X) // 2
	if D & X > 0:
		print(-1)
	else:
		a = D
		for i in range(50, -1, -1):
			if X >> i & 1 and a + (1 << i) < A[0]:
				a += 1 << i
		if a > 0 and A[0] >= a:
			print(A[0] - a)
		else:
			print(-1)


INF = 10 ** 18

def calc(a, b, xor):
	if (a, b, xor) in memo:
		return memo[a, b, xor]
	if a & 1 ^ b & 1 != xor & 1:
		return INF
	if xor == 0:
		if a < b:
			return INF
		else:
			return (a - b) // 2
	x = 2 * calc(a // 2, b // 2, xor // 2)
	y = 2 * calc((a - 1) // 2, (b + 1) // 2, xor // 2) + 1
	memo[a, b, xor] = min(x, y)
	return memo[a, b, xor]
n = int(input())
arr = list(map(int, input().split()))
(a, b) = (arr[0], arr[1])
xor = 0
for i in range(2, n):
	xor ^= arr[i]
memo = {}
ans = calc(a, b, xor)
if ans >= a:
	print(-1)
else:
	print(ans)


n = int(input())
a = list(map(int, input().split()))
x = 0
for i in a[2:]:
	x ^= i
m = (a[0] + a[1] - x) // 2
if a[0] + a[1] != x + m * 2 or m > a[0] or x & m != 0:
	print(-1)
	return ()
l = 1 << max(x.bit_length(), m.bit_length()) + 1
while l > 0:
	if x & l != 0 and m | l <= a[0]:
		m |= l
	l >>= 1
print(a[0] - m if m != 0 else -1)


import sys
N = int(input())
A = list(map(int, input().split()))
c = 0
for i in range(2, N):
	c ^= A[i]
a = A[0]
b = A[1]
remc = a + b
ori = 0
lis = [None] * 60
for i in range(59, -1, -1):
	np = 2 ** i
	if np & c > 0:
		lis[i] = -1
		remc -= np
	elif remc >= np * 2:
		remc -= np * 2
		lis[i] = 1
		ori |= np
	else:
		lis[i] = 0
if remc != 0 or ori > a:
	print(-1)
	sys.exit()
ao = ori
for i in range(59, -1, -1):
	np = 2 ** i
	if lis[i] == -1 and ao | np <= a:
		ao |= np
if ao > 0:
	print(a - ao)
else:
	print(-1)


def main():
	n = int(input())
	a = list(map(int, input().split()))
	xor = 0
	for i in range(2, n):
		xor ^= a[i]
	s = a[0] + a[1]
	dp = [[[-1 for k in range(2)] for j in range(2)] for i in range(45)]
	p = a[0]
	dp[0][0][0] = 0
	for i in range(44):
		crrx = xor & 1
		crrs = s & 1
		crrp = p & 1
		for j in range(2):
			for k in range(2):
				if dp[i][j][k] == -1:
					continue
				for nxtp in range(2):
					for nxtq in range(2):
						nxti = i + 1
						nxtj = 0
						nxtk = k
						if nxtp ^ nxtq != crrx:
							continue
						nxts = nxtp + nxtq + j
						if nxts % 2 != crrs:
							continue
						if nxts >= 2:
							nxtj = 1
						if crrp < nxtp:
							nxtk = 1
						elif crrp == nxtp:
							nxtk = k
						else:
							nxtk = 0
						dp[nxti][nxtj][nxtk] = max(dp[nxti][nxtj][nxtk], dp[i][j][k] + (1 << i) * nxtp)
		xor //= 2
		s //= 2
		p //= 2
	if dp[-1][0][0] > 0:
		print(a[0] - dp[-1][0][0])
	else:
		print(-1)
main()


import sys
sys.setrecursionlimit(10 ** 7)
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right
from collections import deque
from collections import Counter
from itertools import accumulate, combinations, permutations
from heapq import heapify, heappop, heappush
from functools import lru_cache
from decimal import Decimal

def input():
	x = sys.stdin.readline()
	return x[:-1] if x[-1] == '\n' else x

def printl(li):
	_ = print(*li, sep='\n') if li else None

def argsort(s, return_sorted=False):
	inds = sorted(range(len(s)), key=lambda k: s[k])
	if return_sorted:
		return (inds, [s[i] for i in inds])
	return inds

def alp2num(c, cap=False):
	return ord(c) - 97 if not cap else ord(c) - 65

def num2alp(i, cap=False):
	return chr(i + 97) if not cap else chr(i + 65)

def matmat(A, B):
	(K, N, M) = (len(B), len(A), len(B[0]))
	return [[sum([A[i][k] * B[k][j] for k in range(K)]) for j in range(M)] for i in range(N)]

def matvec(M, v):
	(N, size) = (len(v), len(M))
	return [sum([M[i][j] * v[j] for j in range(N)]) for i in range(size)]

def T(M):
	(n, m) = (len(M), len(M[0]))
	return [[M[j][i] for j in range(n)] for i in range(m)]

def main():
	mod = 1000000007
	N = int(input())
	A = tuple(map(int, input().split()))
	ref = 0
	for i in range(2, N):
		ref ^= A[i]
	a0 = A[0]
	a1 = A[1]
	ans = 0
	INF = 10 ** 13

	@lru_cache(None)
	def dfs(a0, a1, ref):
		inf = INF
		if a0 & 1 ^ a1 & 1 != ref & 1:
			return inf
		if a0 < 0:
			return inf
		if ref == 0:
			return inf if a0 < a1 else (a0 - a1) // 2
		a01 = a0 & 1
		a11 = a1 & 1
		ref1 = ref & 1
		ans = inf
		if a01 ^ a11 == ref1:
			ans = min(ans, 2 * dfs(a0 >> 1, a1 >> 1, ref >> 1))
		ans = min(ans, 2 * dfs((a0 - 1) // 2, (a1 + 1) // 2, ref >> 1) + 1)
		return ans
	x = dfs(a0, a1, ref)
	if x >= a0:
		print(-1)
	else:
		print(x)

def __starting_point():
	main()
__starting_point()


N = int(input())
A = list(map(int, input().split()))
X = 0
for i in range(2, N):
	X ^= A[i]
S = A[0] + A[1]
c = 0
l = []
for i in range(40):
	if 2 ** i & X == 2 ** i:
		c += 2 ** i
	else:
		l.append(2 ** i)
S -= c
a = 0
b = 0
for n in l:
	if 2 * n & S == 2 * n:
		a += n
		b += n
if a + b == S:
	for i in range(40, -1, -1):
		if 2 ** i & c == 2 ** i and a + 2 ** i < A[0]:
			a += 2 ** i
	if a != 0:
		ans = max(A[0] - a, -1)
	else:
		ans = -1
else:
	ans = -1
print(ans)


N = int(input())
A = list(map(int, input().split()))
XOR = 0
for el in A[2:]:
	XOR ^= el
if (A[0] + A[1] - XOR) % 2 != 0:
	print(-1)
	exit(0)
AND = (A[0] + A[1] - XOR) // 2
if XOR & AND != 0:
	print(-1)
	exit(0)
ok = False
u = 0
v = 0
bits = list()
for bit in range(60, -1, -1):
	if XOR >> bit & 1 == 0 and AND >> bit & 1 == 1:
		u |= 1 << bit
		v |= 1 << bit
	elif XOR >> bit & 1 == 1 and AND >> bit & 1 == 0:
		bits.append(bit)
for bit in bits:
	if u | 1 << bit <= A[0]:
		u |= 1 << bit
if u > A[0] or u == 0:
	print(-1)
	exit(0)
print(A[0] - u)


n = int(input())
a = list(map(int, input().split()))
S = sum(a[:2])
X = 0
for i in range(2, n):
	X ^= a[i]
if S - X < 0 or (S - X) % 2 != 0:
	print(-1)
	exit(0)
D = (S - X) // 2
if D > a[0] or D & X:
	print(-1)
	exit(0)
res = D
for i in range(60, -1, -1):
	if X & 1 << i:
		Q = res | 1 << i
		if Q <= a[0]:
			res = Q
print(-1 if res == 0 else a[0] - res)


import sys
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
S = A[0] + A[1]
X = 0
for i in range(2, N):
	X ^= A[i]
K = S - X
if K & 1:
	print(-1)
else:
	K >>= 1
	if K & X or K > A[0]:
		print(-1)
	else:
		Y = 0
		for i in range(60, -1, -1):
			if X & 1 << i and Y + (1 << i) ^ K <= A[0]:
				Y += 1 << i
		Y = Y ^ K
		if not Y:
			print(-1)
		else:
			print(A[0] - Y)


import sys
INF = float('inf')
MOD = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
input = lambda : sys.stdin.readline().rstrip()
from functools import reduce
from operator import xor
from itertools import product

def resolve():
	n = int(input())
	A = list(map(int, input().split())) + [0]
	a = A[0]
	s = sum(A[:2])
	u = reduce(xor, A[2:])
	if s < u or s + u & 1:
		print('-1')
		return
	v = (s - u) // 2
	dp = [0, -INF]
	for d in range(60, -1, -1):
		ndp = [-INF, -INF]
		ad = a >> d & 1
		ud = u >> d & 1
		vd = v >> d & 1
		for (lt, xd, yd) in product(range(2), repeat=3):
			if not lt and ad < xd:
				continue
			if xd ^ yd != ud:
				continue
			if xd & yd != vd:
				continue
			nlt = max(lt, ad > xd)
			ndp[nlt] = max(ndp[nlt], dp[lt] + (xd << d))
		dp = ndp
	pile = max(dp)
	if pile <= 0:
		print(-1)
	else:
		print(a - pile)
resolve()


import sys
input = sys.stdin.readline

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))

def main():
	mod = 10 ** 9 + 7
	inf = 10 ** 13
	N = I()
	A = LI()
	allx = 0
	for i in range(N):
		allx = allx ^ A[i]
	if allx == 0:
		print(0)
		exit()
	if A[0] == 1:
		print(-1)
		exit()
	M = 45

	def calc(S, T):
		if T > S:
			return False
		if (S - T) % 2 == 1:
			return False
		if T == S:
			cnt = 0
			m = inf
			T2 = T
			a = 0
			b = 0
			for j in range(M, -1, -1):
				p = 1 << j
				if p <= T2:
					T2 -= p
					m = p
					cnt += 1
					if a + p <= A[0]:
						a += p
					else:
						b += p
			if cnt == 1:
				return False
			if a == 0:
				return False
			if b == 0:
				a -= m
			return a
		if (S - T) // 2 > A[0]:
			return False
		T2 = T
		S2 = (S - T) // 2
		a = S2
		b = S2
		for i in range(M, -1, -1):
			p = 1 << i
			ft = 0
			fs = 0
			if p <= T2:
				T2 -= p
				ft = 1
			if p <= S2:
				S2 -= p
				fs = 1
			if ft and fs:
				return False
			if ft:
				if a + p <= A[0]:
					a += p
				else:
					b += p
		return a
	ans = inf
	for i in range(1, N):
		S = A[0] + A[i]
		T = A[0] ^ A[i] ^ allx
		a = calc(S, T)
		if a != 0:
			ans = min(ans, A[0] - a)
	if ans == inf:
		ans = -1
	print(ans)
main()