Sereja and Dima play a game. The rules of the game are very simple. The players have n cards in a row. Each card contains a number, all numbers on the cards are distinct. The players take turns, Sereja moves first. During his turn a player can take one card: either the leftmost card in a row, or the rightmost one. The game ends when there is no more cards. The player who has the maximum sum of numbers on his cards by the end of the game, wins.

Sereja and Dima are being greedy. Each of them chooses the card with the larger number during his move.

Inna is a friend of Sereja and Dima. She knows which strategy the guys are using, so she wants to determine the final score, given the initial state of the game. Help her.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 1000) — the number of cards on the table. The second line contains space-separated numbers on the cards from left to right. The numbers on the cards are distinct integers from 1 to 1000.


-----Output-----

On a single line, print two integers. The first number is the number of Sereja's points at the end of the game, the second number is the number of Dima's points at the end of the game.


-----Examples-----
Input
4
4 1 2 10

Output
12 5

Input
7
1 2 3 4 5 6 7

Output
16 12



-----Note-----

In the first sample Sereja will take cards with numbers 10 and 2, so Sereja's sum is 12. Dima will take cards with numbers 4 and 1, so Dima's sum is 5.

Difficulty: interview

Starter code:

Solutions:
n=int(input())
a=list(map(int,input().split()))
b=True
l=0
r=n-1
ans1=0
ans2=0
while l<=r:
    if a[l]>a[r]:
        if b:
            ans1+=a[l]
            b=False
        else:
            ans2+=a[l]
            b=True
        l+=1
    else:
        if b:
            ans1+=a[r]
            b=False
        else:
            ans2+=a[r]
            b=True   
        r-=1
print(ans1,ans2)

n=int(input())
a=list(map(int,input().split()))
l=0
r=n-1
b=[0,0]
for i in range(n):
    if a[l]>a[r]:
        b[i%2]+=a[l]
        l+=1
    else:
        b[i%2]+=a[r]
        r-=1
print(b[0],b[1])

from collections import deque

n = int(input())

numbers = deque()
aux = list(map(int, input().split()))

for i in range(n):
    numbers.append(aux[i])

ser, dim  = 0, 0

for i in range(n):
    if numbers[0] > numbers[-1]:
        if i % 2 == 0:
            ser += numbers[0]
        else:
            dim += numbers[0]
        numbers.popleft()
    else:
        if i % 2 == 0:
            ser += numbers[-1]
        else:
            dim += numbers[-1]
        numbers.pop()

print(ser, dim)

n = int(input())
a = list(map(int, input().split()))
b = [0, 0]
c = 0
while n:
    if a[0] > a[n-1]:
        b[c] += a[0]
        a = a[1:n]
    else:
        b[c] += a[n-1]
        a = a[0:n-1]
    c = 1-c
    n -= 1
print("%d %d" % (b[0], b[1]))



n = input()
line = list(map(int, input().split()))
sum = [0, 0]
player = 1
while len(line) > 0:
    if line[0] > line[-1]:
        sum[player] += line[0]
        player = not player
        line.remove(line[0])
    else:
        sum[player] += line[-1]
        player = not player
        line.remove(line[-1])
print(sum[1], sum[0])

n=int(input())
a=list(map(int,input().split()))
s=0;d=0;
for i in range(1,n+1):
    maxi=max(a[0],a[-1])
    ind=a.index(maxi)
    a.pop(ind)
    if(i%2!=0):
        s+=maxi
    else:
        d+=maxi
print(s,d)
        
        
    


n = int(input())
s1=0
s2=0
a = list(map(int, input().split()))
r = n-1
l = 0
k = 0
for i in range(n):
    if a[l]>a[r]:
        if k == 0:
            s1+=a[l]
            k = 1
        else:
            s2+=a[l]
            k = 0
        l += 1
        
    else:
        if k == 0:
            s1+=a[r]
            k = 1
        else:
            s2+=a[r]
            k = 0
        r -= 1
print(s1,s2)

import sys
def main():
    
    l=sys.stdin.readline()

    l=sys.stdin.readline()
    l=l.split()
    for i in range(len(l)):
        l[i]=int(l[i])
    
    ser=len(l)-1
    dim=0
    s_ser=0
    s_dim=0
 
    while ser>dim:
        
        if l[dim] > l[ser]:
            s_ser+=l[dim]
            dim+=1
        else:
            s_ser+=l[ser]
            ser-=1
        if l[dim] > l[ser]:
            s_dim+=l[dim]
            dim+=1
        else:
            s_dim+=l[ser]
            ser-=1
       
    if ser==dim:
        s_ser+=l[ser]
    print (s_ser , s_dim)

def __starting_point():
    main()
__starting_point()

import sys


def main():
    left = 0
    right = int(input()) - 1
    arr = [int(k) for k in input().split()]
    score = [0, 0]
    i = 0

    while left != right:
        if arr[left] > arr[right]:
            score[i] += arr[left]
            left += 1
        else:
            score[i] += arr[right]
            right -= 1
        i += 1
        i %= 2

    score[i] += arr[left]
    print(score[0], score[1])


def __starting_point():
    main()

__starting_point()

n = int(input())
test = []
test = list(map(int, input().split()))
left = 0
right = len(test)-1

a = []
b = []

while test:
    if test[left] > test[right]:
        a.append(test[left])
        test.remove(test[left])
        right = len(test)-1
    else:
        a.append(test[right])
        test.remove(test[right])
        right = len(test)-1
    if test:
        if test[left] > test[right]:
            b.append(test[left])
            test.remove(test[left])
            right = len(test)-1
        else:
            b.append(test[right])
            test.remove(test[right])
            right = len(test)-1

print(sum(a), sum(b))


n=int(input())
z=[int(x) for x in input().split()]

tot1=0
tot2=0

if (len(z)%2==0):
    while (len(z)>0):
        tot1+= max(z[0],z[-1])
        z.remove(max(z[0],z[-1]))
        tot2+= max(z[0],z[-1])
        z.remove(max(z[0],z[-1]))
    print(str(tot1)+" "+str(tot2))

else:
    while(1):
        tot1+=max(z[0],z[-1])
        z.remove(max(z[0],z[-1]))
        if (len(z)==0):
            break
        else:
            tot2+=max(z[0],z[-1])
            z.remove(max(z[0],z[-1]))
            if (len(z)==0):
                break
            else:
                continue        
    print(str(tot1)+" "+str(tot2))
                 


n = int(input())
cards = list(map(int, input().split()))
s = True
d = False
ps = 0
pd = 0
while len(cards) > 0:
    if s:
        if cards[0] > cards[-1]:
            ps += cards[0]
            t = 0
        else:
            ps += cards[-1]
            t = -1
        s = False
        d = True
        cards.pop(t)
    elif d:
        if cards[0] > cards[-1]:
            pd += cards[0]
            t = 0
        else:
            pd += cards[-1]
            t = -1
        s = True
        d = False
        cards.pop(t)

print(ps, pd)

n=int(input())
a=[0]*1010
name=1
ser=0
dim=0
a=list(map(int, input().split()))
flag=1
while n>1:
    if name%2!=0:
        ser+=max(a[0],a[n-1])
        if a[0]>a[n-1]:
            del a[0]
        else:
            del a[n-1]
    else:
        dim+=max(a[0],a[n-1])
        if a[0]>a[n-1]:
            del a[0]
        else:
            del a[n-1]
    n-=1
    name+=1
if name%2!=0:
    ser+=a[0]
else:
    dim+=a[0]
print(ser,dim)
        


num=int(input())
txt=input()
points=txt.split(" ")
score=[0,0]
turn=0
while len(points)>0:
    maxp=max(int(points[0]),int(points[-1]))
    score[turn]+=maxp
    points.remove(str(maxp))
    turn=(turn+1)%2
print(score[0],score[1])

from collections import deque

__author__ = 'asmn'
n=int(input())

a=deque(map(int,input().split()))
s=[0,0]
now=0
while len(a) > 0:
    if a[0] > a[-1]:
        s[now] += a.popleft()
    else:
        s[now] +=a.pop()
    now = 1-now

print(s[0],s[1])

n=int(input())
a=list(map(int,input().split()))
i=0
j=n-1
b=[0]*2
t=0
while i<=j:
    if a[i]>a[j]:
        b[t]+=a[i]
        i+=1
    else:
        b[t]+=a[j]
        j-=1
    t^=1
print(b[0],b[1])



input()
input_raw = [int(x) for x in input().split(' ')]

s = 0
d = 0
i = True

while input_raw != []:
    if input_raw[0] > input_raw[-1]:
        cur = input_raw[0]
        del(input_raw[0])
    else:
        cur = input_raw[-1]
        del(input_raw[-1])

    if i:
        s += cur
        i = False
    else:
        d += cur
        i = True

print(s, d)

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

from sys import stdin, stdout

def solve(c, n):
	s_res = 0
	d_res = 0
	turn = 's'
	while len(c) > 0:
		left_is_max = c[0] > c[-1]
		max_card = c.pop(0 if left_is_max else -1)
		if turn == 's':
			s_res += max_card
			turn = 'd'
		else:
			d_res += max_card
			turn = 's'
	return (s_res, d_res)

def __starting_point():
	n_s = stdin.readline()
	cards_s = stdin.readline().split(' ')
	n = int(n_s)
	cards = [int(c) for c in cards_s]
	result = solve(cards, n)
	print(result[0], result [1])
__starting_point()

num = int(input())
cards = input()
cards = [int(i) for i in cards.split()]

begin = 0
end = num-1

sereja = 0
dima = 0
turn = 0

for i in range(0,num):
    if turn == 0:
        if cards[begin] > cards[end]:
            sereja += cards[begin]
            begin += 1
        else:
            sereja += cards[end]
            end -= 1
        turn = 1

    else:
        if cards[begin] > cards[end]:
            dima += cards[begin]
            begin += 1
        else:
            dima += cards[end]
            end -= 1
        turn = 0

print(sereja, dima)


# -*- coding: utf-8 -*-
import sys

n = int(sys.stdin.readline())
a = [int(x) for x in sys.stdin.readline().split(' ')]

sum = [0, 0]
start = 0
end = n-1
i = 0
while start != end:
    if a[start] >= a[end]:
        sum[i] += a[start]
        start += 1
    else:
        sum[i] += a[end]
        end -= 1
    i = (i+1) % 2
sum[i] += a[start]
print(sum[0], sum[1])


# -*- coding: utf-8 -*-
import sys

n = int(sys.stdin.readline())
a = [int(x) for x in sys.stdin.readline().split(' ')]

sum = [0, 0]
i, start, end = 0, 0, n-1
while start <= end:
    if a[start] >= a[end]:
        sum[i] += a[start]
        start += 1
    else:
        sum[i] += a[end]
        end -= 1
    i ^= 1
print(sum[0], sum[1])


import sys


flag = 0
sereja = 0
dima = 0


n = int(sys.stdin.readline())
lista = sys.stdin.readline().split()

for i  in range(n):
    lista[i] = int(lista[i])

actual = 0
while len(lista)>0:
    if len(lista) == 1:
        actual = lista.pop()
    else:
        if lista[0]>lista[-1]:
            actual = lista.pop(0)
        else:
            actual = lista.pop()
    if flag == 0:
        sereja += actual
        flag = 1
    else:
        dima +=actual
        flag = 0


print(sereja," ",dima)


#-------------------------------------------------------------------------------
# Name:        Ð Â Ð’Â Ð â€™Ð’Â Ð Â Ð Ð‹Ð â€™Ð’Â˜Ð Â Ð’Â Ð â€™Ð’Â Ð Â Ð Ð‹Ð Ð†Ð â€šÐ¡Ñ›Ð Â Ð’Â Ð â€™Ð’Â Ð Â Ð¡Ñ›Ð Ð†Ð â€šÐ’Â˜Ð Â Ð’Â Ð Â Ð â€¹Ð Â Ð Ð‹Ð Ð†Ð â€šÐ¡Ñ™Ð Â Ð’Â Ð â€™Ð’Â Ð Â Ð²Ð‚â„¢Ð â€™Ð’Â»Ð Â Ð’Â Ð Â Ð â€¹Ð Â Ð’Â Ð Â Ð²Ð‚Â°1
# Purpose:
#
# Author:      Anatoliy
#
# Created:     30.09.2013
# Copyright:   (c) Anatoliy 2013
# Licence:     <your licence>
#-------------------------------------------------------------------------------

def main():
    number_of_elements = int(input())
    s = input()
    s_list = s.split(" ")
    for i in range(0, number_of_elements):
        s_list[i] = int(s_list[i])


    sereja = 0
    dima = 0

    for i in range(0, int(number_of_elements/2)):
        if s_list[0] > s_list[-1]:
            sereja = sereja + s_list.pop(0)
        else:
            sereja = sereja + s_list.pop(-1)
        if s_list[0] > s_list[-1]:
            dima = dima + s_list.pop(0)
        else:
            dima = dima + s_list.pop(-1)
    sereja = sereja + sum(s_list)
    print(str(sereja) + " " + str(dima))



def __starting_point():
    main()

__starting_point()

n = int(input())
a = list(map(int,input().split()))
i = 0
j = n - 1
now = 1
ans1 = 0
ans2 = 0
while (i <= j):
	cur = 0
	if (a[i] > a[j]):
		cur = a[i]
		i += 1
	else:
		cur = a[j]
		j -= 1
	if (now == 1):
		ans1 += cur
	else:
		ans2 += cur
	now = 1 - now
print(ans1, ans2)