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: interview

Starter code:

Solutions:
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)


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)
#print(bob)

print(ali[0], bob[0], sep=' ')
	


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])

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())
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])



import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

n=int(input())

pie=list(map(int,input().split()))

def dp(i):
    # best result for this player
    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)

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
#                nC, nO
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()]

suffix = [a[-1]]
tok = [a[-1]]
tol = [0]
best = [a[-1]]

for x in reversed(a[:-1]):
	# keep
	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(best, tok, tol, suffix)
print(suffix[-1] - best[-1], best[-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)


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])

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()

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))

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 = [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)


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()))
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])

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)



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 ))



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 the last element gives the highest 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()

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:
    # print(n)
    n.reverse()
    f = max(n[0], n[1]) # f2
    s = n[0] + n[1] # s2
    for i in range(2, N):
        f = max(n[i] + s - f, f)
        s += n[i]
    # print(f)
    # print(s)
    ans = [s-f, f]
        
print(" ".join(map(str,ans)))

# assume f(n) is the optimal strategy for the remaning n pies, x_n, x_n-1, ...., x_1
#
# s(n) = sum(x_1,..., x_n)
# f(1) = x1
# f(2) = max(x2, x1)
# f(3) = max(x3 + s(2) - f(2), f(2))
# f(4) = max(x4 + s(3) - f(3), f(3))


'''
codeforces.com/problemset/problem/859/C
author: latesum
'''
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())
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())
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)

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])