You may have heard of the pie rule before. It states that if two people wish to fairly share a slice of pie, one person should cut the slice in half, and the other person should choose who gets which slice. Alice and Bob have many slices of pie, and rather than cutting the slices in half, each individual slice will be eaten by just one person.

The way Alice and Bob decide who eats each slice is as follows. First, the order in which the pies are to be handed out is decided. There is a special token called the "decider" token, initially held by Bob. Until all the pie is handed out, whoever has the decider token will give the next slice of pie to one of the participants, and the decider token to the other participant. They continue until no slices of pie are left.

All of the slices are of excellent quality, so each participant obviously wants to maximize the total amount of pie they get to eat. Assuming both players make their decisions optimally, how much pie will each participant receive?


-----Input-----

Input will begin with an integer N (1 ≤ N ≤ 50), the number of slices of pie. 

Following this is a line with N integers indicating the sizes of the slices (each between 1 and 100000, inclusive), in the order in which they must be handed out.


-----Output-----

Print two integers. First, the sum of the sizes of slices eaten by Alice, then the sum of the sizes of the slices eaten by Bob, assuming both players make their decisions optimally.


-----Examples-----
Input
3
141 592 653

Output
653 733

Input
5
10 21 10 21 10

Output
31 41



-----Note-----

In the first example, Bob takes the size 141 slice for himself and gives the decider token to Alice. Then Alice gives the size 592 slice to Bob and keeps the decider token for herself, so that she can then give the size 653 slice to herself.

Difficulty: MEDIUM
Tags: Dynamic programming

Game theory
Skill types: Dynamic programming

Starter code:

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

def max_revenue(i, a):
	if i == len(a) - 1:
		return (a[-1], 0)
	before = max_revenue(i + 1, a)
	take = (a[i] + before[1], before[0])
	give = (before[0], a[i] + before[1])
	if take[0] > give[0]:
		return take
	else:
		return give
r = max_revenue(0, a)
print(r[1], r[0])


input()
a = b = 0
for q in list(map(int, input().split()))[::-1]:
	if b > a + q:
		a += q
	else:
		(b, a) = (a + q, b)
print(a, b)


import sys
cache = {}

def max_possible(pie_slices, current_slice, pre_sums):
	if current_slice in cache:
		return cache[current_slice]
	if len(pie_slices) - 1 == current_slice:
		return pie_slices[current_slice]
	max_score = -1
	for cs in range(current_slice, len(pie_slices) - 1):
		score = pie_slices[cs] + pre_sums[cs + 1] - max_possible(pie_slices, cs + 1, pre_sums)
		if score > max_score:
			max_score = score
	if max_score < pie_slices[-1]:
		max_score = pie_slices[-1]
	cache[current_slice] = max_score
	return max_score

def main():
	n = int(sys.stdin.readline().strip())
	pie_slices = [int(tok) for tok in sys.stdin.readline().strip().split()]
	pre_sums = [sum(pie_slices[i:]) for i in range(len(pie_slices))]
	b = max_possible(pie_slices, 0, pre_sums)
	print(sum(pie_slices) - b, b)

def __starting_point():
	main()
__starting_point()


import math

def main():
	n = int(input())
	slices = [int(x) for x in input().split()]
	dp = [[[0, 0], [0, 0]] for i in range(n)]
	dp[-1][0] = [slices[-1], 0]
	dp[-1][1] = [0, slices[-1]]
	for i in range(n - 2, -1, -1):
		for j in range(0, 2):
			take = slices[i] + dp[i + 1][1 - j][j]
			do_not_take = dp[i + 1][j][j]
			if take > do_not_take:
				dp[i][j][j] = take
				dp[i][j][1 - j] = dp[i + 1][1 - j][1 - j]
			else:
				dp[i][j][j] = do_not_take
				dp[i][j][1 - j] = slices[i] + dp[i + 1][j][1 - j]
	print(dp[0][1][0], dp[0][1][1])

def __starting_point():
	main()
__starting_point()


n = int(input())
a = list(map(int, input().split()))
a = a[::-1]
d = 0
for i in range(len(a)):
	d = max(0 + d, a[i] + (sum(a[:i]) - d))
print(sum(a) - d, d)


def check(i, bob):
	if i >= n:
		return (0, 0)
	if dp[bob][i] != (-1, -1):
		return dp[bob][i]
	if bob:
		x = check(i + 1, False)
		y = check(i + 1, True)
		if x[0] + arr[i] >= y[0]:
			ret = (x[0] + arr[i], x[1])
		else:
			ret = (y[0], y[1] + arr[i])
	else:
		x = check(i + 1, True)
		y = check(i + 1, False)
		if x[1] + arr[i] >= y[1]:
			ret = (x[0], x[1] + arr[i])
		else:
			ret = (y[0] + arr[i], y[1])
	dp[bob][i] = ret
	return ret
n = int(input())
dp = [(-1, -1)] * n
dp = [dp, dp.copy()]
arr = list(map(int, input().split()))
ans = check(0, True)
print(ans[1], ans[0])


n = int(input())
a = list(map(int, input().split()))
first = [0] * n
second = [0] * n
a.reverse()
first[0] = a[0]
for i in range(1, n):
	if a[i] + second[i - 1] >= first[i - 1]:
		first[i] = a[i] + second[i - 1]
		second[i] = first[i - 1]
	else:
		first[i] = first[i - 1]
		second[i] = a[i] + second[i - 1]
print(second[n - 1], first[n - 1])


n = int(input())
arr = list(map(int, input().split()))
if n == 1:
	print(0, arr[0])
else:
	dp = [[0 for j in range(2)] for i in range(n)]
	dp[n - 1][0] = arr[n - 1]
	for i in range(n - 2, -1, -1):
		dp[i][0] = max(arr[i] + dp[i + 1][1], dp[i + 1][0])
		dp[i][1] = min(arr[i] + dp[i + 1][1], dp[i + 1][0])
	print(dp[0][1], dp[0][0])


n = int(input())
slices = list(map(int, input().split()))[::-1]
(a, b) = (0, 0)
for c in slices:
	if b > a + c:
		a += c
	else:
		(b, a) = (a + c, b)
print(a, b)


n = int(input())
a = list(map(int, input().split()))
sa = [0] * n
dp = [0] * n
sa[-1] = a[-1]
for i in range(n - 1)[::-1]:
	sa[i] = sa[i + 1] + a[i]
dp[-1] = a[-1]
for i in range(0, n - 1)[::-1]:
	dp[i] = max(dp[i + 1], sa[i + 1] - dp[i + 1] + a[i])
print(sa[0] - dp[0], dp[0])


n = int(input())
pieces = list(map(int, input().split()))
reversed_pieces = list(reversed(pieces))
TOTAL = []
current_total = 0
for piece in reversed_pieces:
	current_total += piece
	TOTAL.append(current_total)
HAS_TOKEN = 0
NO_TOKEN = 1
dp_alice = [[0] * n, [0] * n]
dp_bob = [[0] * n, [0] * n]
dp_alice[HAS_TOKEN][0] = dp_bob[HAS_TOKEN][0] = reversed_pieces[0]
dp_alice[NO_TOKEN][0] = dp_bob[NO_TOKEN][0] = 0
for i in range(1, n):
	dp_alice[HAS_TOKEN][i] = max(dp_alice[HAS_TOKEN][i - 1], dp_alice[NO_TOKEN][i - 1] + reversed_pieces[i])
	dp_bob[HAS_TOKEN][i] = max(dp_bob[HAS_TOKEN][i - 1], dp_bob[NO_TOKEN][i - 1] + reversed_pieces[i])
	dp_alice[NO_TOKEN][i] = TOTAL[i] - dp_bob[HAS_TOKEN][i]
	dp_bob[NO_TOKEN][i] = TOTAL[i] - dp_alice[HAS_TOKEN][i]
print(dp_alice[NO_TOKEN][-1], dp_bob[HAS_TOKEN][-1])


n = int(input())
a = list(map(int, input().split()))
x = s = 0
for ai in reversed(a):
	x = max(x, ai + s - x)
	s += ai
print(s - x, x)


import os
import sys
from io import BytesIO, IOBase

def main():
	import bisect
	import math
	alpha = 'abcdefghijklmnopqrstuvwxyz'
	ALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
	inf = 1e+17
	mod = 10 ** 9 + 7
	Max = 10 ** 6
	primes = []
	prime = [True for i in range(Max + 1)]
	p = 2
	while p * p <= Max + 1:
		if prime[p] == True:
			for i in range(p * p, Max + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, Max + 1):
		if prime[p]:
			primes.append(p)

	def factorial(n):
		f = 1
		for i in range(1, n + 1):
			f = f * i % mod
		return f

	def ncr(n, r):
		num = den = 1
		for i in range(r):
			num = num * (n - i) % mod
			den = den * (i + 1) % mod
		return num * pow(den, mod - 2, mod) % mod

	def solve(n, arr):
		chance = [0] * (n + 1)
		chance[-2] = arr[-1]
		for i in range(n - 2, -1, -1):
			chance[i] = max(chance[i + 1], sum(arr[i + 1:]) - chance[i + 1] + arr[i])
		return (sum(arr) - chance[0], chance[0])
		pass
	t = 1
	ans = []
	for _ in range(t):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ans.append(solve(n, arr))
	for j in range(len(ans)):
		print(ans[j][0], ans[j][1])
	pass
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')
main()


input()
a = b = 0
for (i, x) in enumerate(list(map(int, input().split()))[::-1]):
	if b > a + x:
		a += x
	else:
		(a, b) = (b, a + x)
print(a, b)


n = int(input())
lst = list(map(int, input().split()))
toke = wait = 0
for (i, x) in enumerate(lst[::-1]):
	if toke > wait + x:
		wait += x
	else:
		(toke, wait) = (wait + x, toke)
print(wait, toke)


import sys
read = lambda : sys.stdin.readline().strip()
readi = lambda : map(int, read().split())
from collections import *
n = int(read())
nums = list(readi())
dp = [0] * n
sum = 0
for i in range(1, n + 1):
	i *= -1
	sum += nums[i]
	dp[i] = max(dp[i + 1], sum - dp[i + 1])
print(sum - dp[0], dp[0])


N = int(input())
A = list(map(int, input().split()))
s = [0] * (N + 1)
dp = [0] * (N + 1)
for i in range(N - 1, -1, -1):
	dp[i] = max(A[i] + s[i + 1] - dp[i + 1], dp[i + 1])
	s[i] = s[i + 1] + A[i]
print(s[0] - dp[0], dp[0])


R = lambda : map(int, input().split())
n = int(input())
arr = list(R())
dp = [[0] * 2 for _ in range(n)]
dp[-1][1] = arr[-1]
for i in range(n - 2, -1, -1):
	dp[i][1] = max(dp[i + 1][0] + arr[i], dp[i + 1][1])
	dp[i][0] = min(dp[i + 1][1], dp[i + 1][0] + arr[i])
print(dp[0][0], dp[0][1])


n = int(input())
a = list(map(int, input().split()))
suf = [0] * n
suf[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
	suf[i] = suf[i + 1] + a[i]
dp = [0] * n
dp[n - 1] = a[n - 1]
for i in range(n - 2, -1, -1):
	dp[i] = max(dp[i + 1], suf[i + 1] - dp[i + 1] + a[i])
print(suf[0] - dp[0], dp[0])


N = int(input())
n = list(map(int, input().split(' ')))
if N == 1:
	ans = [0, n[0]]
elif N == 2:
	ans = [min(n), max(n)]
else:
	n.reverse()
	f = max(n[0], n[1])
	s = n[0] + n[1]
	for i in range(2, N):
		f = max(n[i] + s - f, f)
		s += n[i]
	ans = [s - f, f]
print(' '.join(map(str, ans)))


n = int(input())
x = list(map(int, input().split()))
(ma, count) = (0, 0)
for i in range(n - 1, -1, -1):
	ma = max(ma, x[i] + count - ma)
	count += x[i]
print(count - ma, ma)


def go(i, who):
	if dp[i][who] != [-1, -1]:
		return dp[i][who].copy()
	if i == n - 1:
		dp[i][who] = [0, 0]
		dp[i][who][who] = s[i]
		return dp[i][who].copy()
	res1 = go(i + 1, 1 - who)
	res1[who] += s[i]
	res2 = go(i + 1, who)
	res2[1 - who] += s[i]
	if res1[who] > res2[who]:
		dp[i][who] = res1
	else:
		dp[i][who] = res2
	return dp[i][who].copy()
n = int(input())
s = list(map(int, input().split()))
dp = [[[-1, -1], [-1, -1]] for i in range(n)]
go(0, 1)
print(*dp[0][1])


n = int(input())
a = list(map(int, input().split()[::-1]))
f = [[0, 0] for i in range(n)]
f[0][1] = a[0]
f[0][0] = 0
for i in range(1, n):
	f[i][1] = max(f[i - 1][0] + a[i], f[i - 1][1])
	f[i][0] = min(f[i - 1][0] + a[i], f[i - 1][1])
ans = f[-1][1]
print(sum(a) - ans, ans)


def do(n, l):
	if n == 1:
		return [l[0], 0]
	a = do(n - 1, l[1:n])
	if a[1] + l[0] > a[0]:
		return [a[1] + l[0], a[0]]
	return [a[0], a[1] + l[0]]
n = int(input())
l = list(map(int, input().split()))
lsp = do(n, l)
lsp.sort()
print(lsp[0], lsp[1])


import sys
inf = float('inf')
(mod, MOD) = (1000000007, 998244353)

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

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

def input():
	return sys.stdin.readline().strip()
n = int(input())
Arr = get_array()
A = 0
B = 0
for i in reversed(Arr):
	A += i
	if A > B:
		(A, B) = (B, A)
print(A, B)


N = int(input())
a = [int(i) for i in input().split()]
suffix = [a[-1]]
tok = [a[-1]]
tol = [0]
best = [a[-1]]
for x in reversed(a[:-1]):
	keep = x + suffix[-1] - best[-1]
	give = best[-1]
	best.append(max(keep, give))
	tok.append(keep)
	tol.append(give)
	suffix.append(suffix[-1] + x)
print(suffix[-1] - best[-1], best[-1])


n = int(input())
array = input().split()
fin = []
for i in array:
	fin.append(int(i))
dp = [[0 for x in range(len(array))] for y in range(2)]
dp[0][-1] = fin[-1]
dp[1][-1] = 0
i = len(array) - 2
while i >= 0:
	dp[0][i] = max(fin[i] + dp[1][i + 1], dp[0][i + 1])
	dp[1][i] = min(fin[i] + dp[1][i + 1], dp[0][i + 1])
	i -= 1
print(dp[1][0], dp[0][0])


n = int(input())
p = [int(x) for x in input().split(' ')]
a = b = 0
p.reverse()
for pie in p:
	if b > a + pie:
		a += pie
	else:
		(a, b) = (b, a + pie)
print(a, b)


n = int(input())
a = [int(_) for _ in input().split()]
sum1 = 0
sum2 = 0
a.reverse()
for i in a:
	if sum1 >= sum2:
		sum2 += i
	else:
		sum1 += i
print(min(sum1, sum2), max(sum1, sum2))


def pie_rules(S, n):
	K = [0] * (n + 1)
	H = [0] * (n + 1)
	SUM = [0] * (n + 1)
	K[n] = 0
	H[n] = 0
	SUM[n] = 0
	for i in range(n - 1, -1, -1):
		SUM[i] = SUM[i + 1] + S[i]
	for t in range(n - 1, -1, -1):
		K[t] = max(K[t + 1], S[t] + H[t + 1])
		H[t] = SUM[t] - K[t]
	return (K[0], H[0])
n = int(input())
S = list(map(lambda x: int(x), input().split(' ')))
(k, h) = pie_rules(S, n)
print('{} {}'.format(h, k))


n = int(input())
l = [int(i) for i in input().split()]
dp = [[0, 0] for i in range(n)]
dp[n - 1][0] = l[n - 1]
dp[n - 1][1] = 0
s = l[n - 1]
for i in range(n - 2, -1, -1):
	s += l[i]
	dp[i][0] = max(l[i] + dp[i + 1][1], dp[i + 1][0])
	dp[i][1] = min(l[i] + dp[i + 1][1], dp[i + 1][0])
print(s - dp[0][0], dp[0][0])


from os import path
import sys, time
mod = int(1000000000.0 + 7)
from math import ceil, floor, gcd, log, log2, factorial, sqrt
from collections import defaultdict, Counter, OrderedDict, deque
from itertools import combinations, permutations
from string import ascii_lowercase, ascii_uppercase
from bisect import *
from functools import reduce
from operator import mul
maxx = float('inf')
I = lambda : int(sys.stdin.buffer.readline())
lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
S = lambda : sys.stdin.readline().strip('\n')
grid = lambda r: [lint() for i in range(r)]
localsys = 0
start_time = time.time()
nCr = lambda n, r: reduce(mul, range(n - r + 1, n + 1), 1) // factorial(r)

def ceill(n, x):
	return (n + x - 1) // x
T = 0

def solve():
	n = I()
	a = lint()
	(A, B) = (0, 0)
	while a:
		x = a.pop()
		(p, q) = (A, x + B)
		(A, B) = (max(p, q), min(p, q))
	print(B, A)

def run():
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
run()
T = I() if T else 1
for _ in range(T):
	solve()
if localsys:
	print('\n\nTime Elased :', time.time() - start_time, 'seconds')


import traceback
from functools import lru_cache
from itertools import accumulate
try:
	N = int(input())
	nums = list(map(int, input().split()))
	acc = [0] * N
	tot = 0
	for i in range(N - 1, -1, -1):
		tot += nums[i]
		acc[i] = tot

	@lru_cache(None)
	def dp(i):
		if i == N:
			return 0
		return max(dp(i + 1), acc[i] - dp(i + 1))
	b = dp(0)
	a = acc[0] - b
	print(a, b)
except Exception:
	traceback.print_exc()


MAXN = 51
dp = [[-1 for x in range(2)] for y in range(MAXN)]
to = [[-1 for x in range(2)] for y in range(MAXN)]

def solve(act, p, N, v):
	global dp
	global to
	if act == N:
		return 0
	if dp[act][p] == -1:
		ch1 = v[act] - solve(act + 1, 1 - p, N, v)
		ch2 = solve(act + 1, p, N, v) - v[act]
		if ch1 > ch2:
			dp[act][p] = ch1
			to[act][p] = 1 - p
		else:
			dp[act][p] = ch2
			to[act][p] = p
	return dp[act][p]
n = int(input())
v = [int(x) for x in input().split()]
solve(0, 0, n, v)
(act, val) = (0, 0)
for i in range(n):
	if to[i][act] == 1:
		val += v[i]
	act = to[i][act]
print(sum(v) - val, val)


n = int(input())
l = list(map(int, input().split()))
x1 = l[-1]
x2 = 0
i = n - 2
t = [0 for i in range(n)]
p = 0
while i >= 0:
	if p == 0:
		if x2 + l[i] <= x1:
			x2 += l[i]
			p = 0
		else:
			x2 += l[i]
			p = 1
	elif x1 + l[i] <= x2:
		x1 += l[i]
		p = 1
	else:
		x1 += l[i]
		p = 0
	i -= 1
print(min(x1, x2), max(x1, x2))


n = int(input())
l = list(map(int, input().split()))
if n == 1:
	print(0, l[0])
	exit()
l.reverse()
y = l[0]
x = l[1]
for i in range(2, n):
	if x > y:
		y += l[i]
	else:
		x += l[i]
if x > y:
	(x, y) = (y, x)
print(x, y)


N = int(input())
List = [int(x) for x in input().split()]
Alice = 0
Bob = 0
for i in range(N - 1, -1, -1):
	if Bob > Alice + List[i]:
		Alice += List[i]
	else:
		(Alice, Bob) = (Bob, Alice + List[i])
print(Alice, Bob)


n = int(input())
vs = list(map(int, input().split(' ')))
rs = [0, 0]
for i in range(n - 1, -1, -1):
	rs = [min(vs[i] + rs[0], rs[1]), max(vs[i] + rs[0], rs[1])]
print(sum(vs) - rs[1], rs[1])


n = int(input())
m = n
arr = input()
arr = list(map(int, arr.split(' ')))
dp = list('0' * n)
maxi = 0
mini = 0
while m:
	m = m - 1
	if arr[m] + mini > maxi:
		dp[m] = arr[m] + mini
		mini = maxi
		maxi = dp[m]
	elif arr[m] + mini <= maxi:
		dp[m] = maxi
		mini = arr[m] + mini
print(mini, ' ', maxi)


import sys
input = sys.stdin.readline
n = int(input())
pie = list(map(int, input().split()))

def dp(i):
	if i >= len(pie):
		return (0, 0)
	(t1, t2) = dp(i + 1)
	return (max(pie[i] + t2 - t1, t1), t2 + pie[i])
(t1, t2) = dp(0)
print(t2 - t1, t1)


def maximum_pie_consumption(pies):
	c = len(pies) - 1
	toke = wait = 0
	for p in reversed(pies):
		if toke < p + wait:
			(toke, wait) = (wait + p, toke)
		else:
			wait += p
	return (wait, toke)

def __starting_point():
	input()
	pies = list(map(int, input().strip().split()))
	print(' '.join(map(str, maximum_pie_consumption(pies))))
__starting_point()


n = int(input())
pies = list(map(int, input().split()))
bob = 0
alice = 0
for i in pies[::-1]:
	alice += i
	if bob < alice:
		(alice, bob) = (bob, alice)
print(alice, bob)


number_of_cakes = int(input())
cakes = [int(x) for x in input().split()]
cakes_inverse = []
for i in range(number_of_cakes, 0, -1):
	cakes_inverse.append(cakes[i - 1])
alisa_previous_alisa_choose = 0
alisa_previous_bob_choose = 0
bob_previous_alisa_choose = 0
bob_previous_bob_choose = 0
for i in range(number_of_cakes):
	if alisa_previous_alisa_choose > alisa_previous_bob_choose + cakes_inverse[i]:
		alisa_present_alisa_choose = alisa_previous_alisa_choose
		bob_present_alisa_choose = bob_previous_alisa_choose + cakes_inverse[i]
	else:
		alisa_present_alisa_choose = alisa_previous_bob_choose + cakes_inverse[i]
		bob_present_alisa_choose = bob_previous_bob_choose
	if bob_previous_bob_choose > bob_previous_alisa_choose + cakes_inverse[i]:
		bob_present_bob_choose = bob_previous_bob_choose
		alisa_present_bob_choose = alisa_previous_bob_choose + cakes_inverse[i]
	else:
		bob_present_bob_choose = bob_previous_alisa_choose + cakes_inverse[i]
		alisa_present_bob_choose = alisa_previous_alisa_choose
	alisa_previous_alisa_choose = alisa_present_alisa_choose
	alisa_previous_bob_choose = alisa_present_bob_choose
	bob_previous_alisa_choose = bob_present_alisa_choose
	bob_previous_bob_choose = bob_present_bob_choose
print(alisa_present_bob_choose, bob_present_bob_choose)


n = int(input())
arr = list(map(int, input().split()))
(mx, c) = (0, 0)
for i in range(n - 1, -1, -1):
	mx = max(mx, arr[i] + c - mx)
	c += arr[i]
print(c - mx, mx)


import os
import sys
from io import BytesIO, IOBase
import math
from queue import Queue
import itertools
import bisect
import heapq

def main():
	pass
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 binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(int(n))
	return l

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

def maxPrimeFactors(n):
	maxPrime = -1
	while n % 2 == 0:
		maxPrime = 2
		n >>= 1
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			maxPrime = i
			n = n / i
	if n > 2:
		maxPrime = n
	return int(maxPrime)

def countcon(s, i):
	c = 0
	ch = s[i]
	for i in range(i, len(s)):
		if s[i] == ch:
			c += 1
		else:
			break
	return c

def lis(arr):
	n = len(arr)
	lis = [1] * n
	for i in range(1, n):
		for j in range(0, i):
			if arr[i] > arr[j] and lis[i] < lis[j] + 1:
				lis[i] = lis[j] + 1
	maximum = 0
	for i in range(n):
		maximum = max(maximum, lis[i])
	return maximum

def isSubSequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def maxfac(n):
	root = int(n ** 0.5)
	for i in range(2, root + 1):
		if n % i == 0:
			return n // i
	return n

def p2(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def seive(n):
	primes = [True] * (n + 1)
	primes[1] = primes[0] = False
	for i in range(2, n + 1):
		if primes[i]:
			for j in range(i + i, n + 1, i):
				primes[j] = False
	p = []
	for i in range(0, n + 1):
		if primes[i]:
			p.append(i)
	return p

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def denofactinverse(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return pow(fac, m - 2, m)

def numofact(n, m):
	fac = 1
	for i in range(1, n + 1):
		fac = fac * i % m
	return fac

def sod(n):
	s = 0
	while n > 0:
		s += n % 10
		n //= 10
	return s
n = int(input())
l = list(map(int, input().split()))
dp = [0] * n
dp[-1] = l[-1]
for i in range(n - 2, -1, -1):
	dp[i] = max(dp[i + 1], sum(l[i + 1:]) - dp[i + 1] + l[i])
print(sum(l) - dp[0], dp[0])


import traceback
try:
	N = int(input())
	nums = list(map(int, input().split()))
	tot = 0
	dp = 0
	for i in range(N - 1, -1, -1):
		tot += nums[i]
		dp = max(dp, tot - dp)
	b = dp
	a = tot - b
	print(a, b)
except Exception:
	traceback.print_exc()


n = int(input())
arr = list(map(int, input().strip().split()))
sumi = [0 for i in range(n)]
sumi[-1] = arr[-1]
for i in range(n - 2, -1, -1):
	sumi[i] = sumi[i + 1] + arr[i]
dp = [[[0, 0], [0, 0]] for i in range(n + 1)]
dp[n - 1][0] = [arr[-1], 0]
dp[n - 1][1] = [0, arr[-1]]
for i in range(n - 2, -1, -1):
	for j in range(i, n):
		c1 = arr[j] + dp[j + 1][1][0]
		if c1 > dp[i][0][0]:
			dp[i][0] = [c1, sumi[i] - c1]
		c2 = arr[j] + dp[j + 1][0][1]
		if c2 > dp[i][1][1]:
			dp[i][1] = [sumi[i] - c2, c2]
print(*dp[0][1])


n = int(input())
sizes = [int(x) for x in input().split(' ')]
sizes.reverse()
a = b = 0
for i in sizes:
	if i + b > a:
		(a, b) = (i + b, a)
	else:
		b = i + b
print(b, ' ', a)


n = int(input())
a = list(map(int, input().split()))[::-1]
if n != 1:
	(summax, summin) = (max(a[0], a[1]), min(a[0], a[1]))
else:
	summin = 0
	summax = a[0]
for i in range(2, n):
	if summax < summin + a[i]:
		(summax, summin) = (summin + a[i], summax)
	else:
		summin = summin + a[i]
print(summin, summax)


def func(i, x):
	if dp[i][x] == -1:
		if i < n - 1:
			dp[i][x] = max(l[i] + prefix[-1] - prefix[i] - func(i + 1, 1 - x), func(i + 1, x))
		else:
			dp[i][x] = l[i]
	return dp[i][x]
n = int(input())
l = list(map(int, input().split()))
prefix = [0] * n
prefix[0] = l[0]
for i in range(1, n):
	prefix[i] = prefix[i - 1] + l[i]
dp = [[-1, -1] for i in range(n)]
print(prefix[-1] - func(0, 0), func(0, 0))


n = int(input())
v = list(map(int, input().split()))
v.reverse()
ans = [0, 0]
for i in range(n):
	if ans[1] + v[i] > ans[0]:
		t = ans[1] + v[i]
		ans[1] = ans[0]
		ans[0] = t
	else:
		ans[1] += v[i]
print(ans[1], ans[0])


n = int(input())
pies = [int(x) for x in input().split()]
d = {}
d[0] = pies[-1]
for i in range(1, n):
	d[i] = max(sum(pies[-1 - i:]) - d[i - 1], d[i - 1])
s = sum(pies)
res = d[n - 1]
print(s - res, res)


n = int(input())
a = list(map(int, input().split()))
(f, s) = (0, 0)
for i in range(n - 1, -1, -1):
	if s + a[i] < f:
		s += a[i]
	else:
		t = s + a[i]
		s = f
		f = t
print(s, f)


def readints():
	return [int(obj) for obj in input().strip().split()]

class Solver:

	def main(self):
		n = readints()[0]
		a = readints()
		f = [0] * n
		f[n - 1] = a[n - 1]
		for i in range(n - 2, -1, -1):
			f[i] = max(sum(a[i:n]) - f[i + 1], f[i + 1])
		print(sum(a) - f[0], f[0])
Solver().main()


n = int(input())
pie = list(map(int, input().split()))
a = b = 0
for i in reversed(pie):
	if a >= b:
		b += i
	else:
		a += i
print(str(min([a, b])) + ' ' + str(max([a, b])))


n = int(input())
cake = list(map(int, input().split()))
cake.reverse()
pref = [0]
for i in range(n):
	pref.append(cake[i] + pref[-1])
dp = [0] * n
dp[0] = cake[0]
for i in range(1, n):
	dp[i] = max(dp[i - 1], cake[i] + pref[i] - dp[i - 1])
print(pref[n] - dp[n - 1], dp[n - 1])


n = int(input())
d = [[0 for i in range(2)] for i in range(n)]
w = [int(z) for z in input().split()]
w.reverse()
d[0][1] = w[0]
d[0][0] = 0
summ = w[0]
for i in range(1, n):
	summ += w[i]
	d[i][1] = max(d[i - 1][1], d[i - 1][0] + w[i])
	d[i][0] = summ - d[i][1]
print(min(d[n - 1][1], d[n - 1][0]), summ - min(d[n - 1][1], d[n - 1][0]))


def dp(a, i, control):
	if i >= len(a):
		return 0
	if dp_list[control][i] != -1:
		return dp_list[control][i]
	else:
		if control:
			res = max(a[i] + dp(a, i + 1, False), dp(a, i + 1, True))
		else:
			res = min(dp(a, i + 1, True), a[i] + dp(a, i + 1, False))
		dp_list[control][i] = res
		return dp_list[control][i]
n = int(input())
dp_list = [list((-1 for i in range(n))), list((-1 for i in range(n)))]
a = list(map(int, input().split(' ')))
res = dp(a, 0, True)
print('%s %s' % (sum(a) - res, res))


a = int(input())
b = list(map(int, input().split()))
sumA = 0
sumB = 0
for i in range(a):
	if b[a - 1 - i] > abs(sumA - sumB):
		sumA += b[a - 1 - i]
		(sumA, sumB) = (sumB, sumA)
	else:
		sumA += b[a - 1 - i]
print(min(sumA, sumB), max(sumA, sumB))


n = int(input())
p = [int(a) for a in input().split(' ')][::-1]
alice = [[0] * n for a in range(2)]
t = 0
for a in p:
	t += a
alice[0][0] = p[0]
for a in range(1, n):
	if p[a] + alice[1][a - 1] > alice[0][a - 1]:
		alice[0][a] = p[a] + alice[1][a - 1]
		alice[1][a] = alice[0][a - 1]
	else:
		alice[0][a] = alice[0][a - 1]
		alice[1][a] = p[a] + alice[1][a - 1]
print(alice[1][-1], alice[0][-1])


cases = int(input())
pies = input().split()
s = [[0] * cases for i in range(2)]
cases = cases - 1
s[0][cases] = int(pies[cases])
for i in range(cases - 1, -1, -1):
	if int(s[0][i + 1]) < int(s[1][i + 1]) + int(pies[i]):
		s[0][i] = int(s[1][i + 1]) + int(pies[i])
		s[1][i] = s[0][i + 1]
	else:
		s[0][i] = s[0][i + 1]
		s[1][i] = int(s[1][i + 1]) + int(pies[i])
print(s[1][0], s[0][0])


import math
from random import random

def getInt():
	return int(input())

def getInts():
	line = input().split()
	return [int(l) for l in line]

def getFloat():
	return float(input())

def getFloats():
	line = input().split()
	return [float(l) for l in line]

def getStrings():
	line = input().split()
	return line
N = getInt()
values = getInts()
nConsidered = 0
bestForChooserSoFar = [0, 0]
for i in range(len(values)):
	v = values[len(values) - i - 1]
	qsIfTaken = [v + bestForChooserSoFar[1], bestForChooserSoFar[0]]
	qsIfGiven = [bestForChooserSoFar[0], v + bestForChooserSoFar[1]]
	if qsIfTaken[0] >= qsIfGiven[0]:
		bestForChooserSoFar = qsIfTaken
	else:
		bestForChooserSoFar = qsIfGiven
print(str(bestForChooserSoFar[1]) + ' ' + str(bestForChooserSoFar[0]))


n = int(input())
a = [int(i) for i in input().split()]
score = a[n - 1]
total = a[n - 1]
for i in range(n - 2, -1, -1):
	new_score = a[i] + total - score
	if new_score > score:
		score = new_score
	total += a[i]
print(total - score, score)


n = int(input())
s = input()
s1 = s.split()
l = [int(i) for i in s1]
d = {}

def game(i, turn):
	if i == len(l):
		return (0, 0)
	elif (i, turn) in d:
		return d[i, turn]
	else:
		if turn == 0:
			bob = max(l[i] + game(i + 1, 1 - turn)[0], game(i + 1, turn)[0])
			alice = sum(l[i:]) - bob
		else:
			alice = max(l[i] + game(i + 1, 1 - turn)[1], game(i + 1, turn)[1])
			bob = sum(l[i:]) - alice
		d[i, turn] = (bob, alice)
		return (bob, alice)
a = game(0, 0)
s = str(a[1]) + ' ' + str(a[0])
print(s)


n = int(input())
l1 = list(map(int, input().split()))
score = [0]
total = [0]
rest = [0]
for i in range(len(l1) - 1, -1, -1):
	total.append(total[len(l1) - 1 - i] + l1[i])
	score.append(max(l1[i] + total[len(l1) - 1 - i] - score[len(l1) - 1 - i], score[len(l1) - 1 - i]))
print(total[-1] - score[-1], score[-1])


n = int(input())
a = [int(i) for i in input().split()]
a1 = [[-1] * 50, [-1] * 50]

def get(i, fl):
	if i >= n:
		return 0
	if a1[fl][i] != -1:
		return a1[fl][i]
	if fl == 0:
		a1[fl][i] = max(a[i] + get(i + 1, 1), get(i + 1, 0))
	else:
		a1[fl][i] = min(a[i] + get(i + 1, 1), get(i + 1, 0))
	return a1[fl][i]
an = get(0, 0)
print(sum(a) - an, an)


import sys
sys.setrecursionlimit(20000)
inf = float('inf')
mod = 1000000007

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

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

def input():
	return sys.stdin.readline()

def main():
	n = int(input())
	arr = get_array()
	dp = [[0] * 2 for _ in range(n + 1)]
	dp[n][1] = arr[-1]
	dp[n][0] = 0
	for i in range(n - 1, 0, -1):
		dp[i][1] = max(dp[i + 1][0] + arr[i - 1], dp[i + 1][1])
		dp[i][0] = min(dp[i + 1][0] + arr[i - 1], dp[i + 1][1])
	print(sum(arr) - dp[1][1], dp[1][1])
main()


n = int(input())
a = list(map(int, input().split()))
a.reverse()
d = [0 for i in range(n)]
d[0] = [a[0], 0]
for i in range(1, n):
	d[i] = [max(d[i - 1][0], d[i - 1][1] + a[i]), min(d[i - 1][0], d[i - 1][1] + a[i])]
print(d[-1][1], d[-1][0])


ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, ls) = (ii(), ll())
vs = [[0, 0], [0, 0]]
for i in range(n - 1, -1, -1):
	v2 = [vs[0][0], vs[0][1] + ls[i]]
	v3 = [vs[1][0] + ls[i], vs[1][1]]
	vs = [v2, v3] if v2[0] > v3[0] else [v3, v2]
print(*vs[1])


n = int(input())
X = list(map(int, input().split()))
ali = [None] * (n + 1)
bob = [None] * (n + 1)
ali[n] = 0
bob[n] = 0
for i in range(n - 1, -1, -1):
	bob[i] = max(bob[i + 1], ali[i + 1] + X[i])
	ali[i] = sum(X[i:n]) - bob[i]
print(ali[0], bob[0], sep=' ')


n = int(input())
arr = list(map(int, input().split()))
decider = [0] * n
decider[-1] = arr[-1]
sum = arr[n - 1]
for i in range(n - 2, -1, -1):
	sum += arr[i]
	decider[i] = max(decider[i + 1], sum - decider[i + 1])
print(sum - decider[0], decider[0])


n = int(input())
(*a,) = map(int, input().split())
a = a[::-1]
(pref, dp) = ([a[0]], [a[0]])
for i in range(1, n):
	pref.append(pref[i - 1] + a[i])
	dp.append(max(dp[i - 1], pref[i - 1] - dp[i - 1] + a[i]))
print(pref[n - 1] - dp[n - 1], dp[n - 1])


n = int(input())
pies = list(map(int, input().split()))
bestToken = [0] * (n + 1)
bestNoToken = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	if bestNoToken[i + 1] + pies[i] > bestToken[i + 1]:
		bestToken[i] = bestNoToken[i + 1] + pies[i]
		bestNoToken[i] = bestToken[i + 1]
	else:
		bestToken[i] = bestToken[i + 1]
		bestNoToken[i] = pies[i] + bestNoToken[i + 1]
print(bestNoToken[0], bestToken[0])


n = int(input())
s = map(int, input().split())
a = b = 0
for x in list(s)[::-1]:
	if b > a + x:
		a = a + x
	else:
		(b, a) = (a + x, b)
print(a, b)


from sys import stdin, stdout
n = int(stdin.readline())
values = list(map(int, stdin.readline().split()))
dp = [0 for i in range(n)]
dp[-1] = values[-1]
cnt = values[-1]
for i in range(n - 2, -1, -1):
	cnt += values[i]
	dp[i] = max(dp[i + 1], cnt - dp[i + 1])
stdout.write(str(cnt - dp[0]) + ' ' + str(dp[0]))