双人数字游戏

import sys

lines = []

try:
    while True:  # 获取所有输入
        line = sys.stdin.readline().strip()
        if line == "":
            break
        lines.append(line.split())
except:
    pass
N = int(lines[0][0])
l = []
for i in lines[1]:
    l.append(int(i))
del lines


# 搜索路径本质是一个二叉树，那么从树枝向上传播，即可得到最优解
def search(Sa, Sb, l, A, B, term):
    # Sa,Sb为A，B当前的总分
    # l是剩余的数字
    # A,B是A，B上次取的数字
    if len(l) > 0:  # 如果l还没取完
        if term:  # 轮到A
            SaR, SbR = search(Sa + abs(l[0] - A), Sb, l[1:], l[0], B, False)
            SaL, SbL = search(Sa + abs(l[-1] - A), Sb, l[:-1], l[-1], B, False)
            if SaR < SaL:  # A的回合，A会选择对自己有利的
                return SaL, SbL
            else:
                return SaR, SbR
        else:  # 轮到B
            SaR, SbR = search(Sa, Sb + abs(l[0] - B), l[1:], A, l[0], True)
            SaL, SbL = search(Sa, Sb + abs(l[-1] - B), l[:-1], A, l[-1], True)
            if SbR < SbL:  # B的回合，B会选择对自己有利的
                return SaL, SbL
            else:
                return SaR, SbR
    # l被取完后，统计总分
    return Sa, Sb


SaM, SbM = search(0, 0, l, 0, 0, True)
print(SaM, SbM)