题目描述

小晨和小爱玩游戏。游戏规则非常简单。玩家连续有n张牌。每张卡片都包含一个数字，卡片上的所有数字都是不同的。小晨和小爱轮流行动，小晨首先行动。在轮到玩家时，他可以拿一张牌：要么是一排最左边的牌，要么是最右边的一张。当没有更多牌时游戏结束。游戏结束时，卡片上的数字总和最大的玩家获胜。

小晨和小爱很贪婪。他们每个人在游戏过程中总是选择数字较大的牌。

你是小晨和小爱的朋友。你知道小晨和小爱的游戏策略，因此你想根据游戏的初始状态确定最终得分。

输入格式

第一行包含整数n (1 ≤  n  ≤ 1000) — 桌子上的牌数。
第二行包含卡片上从左到右以空格分隔的数字。卡片上的数字是1到1000之间的不同整数。

输出格式

在一行上打印两个整数。第一个数字是比赛结束时小晨的得分，第二个数字是比赛结束时小爱的得分。

4
4 2 1 10

12 5

示例1解释： 小晨 将拿走数字10和2的牌，因此 小晨 的总和为12。小爱 将拿走数字4和1 的牌，因此 小爱 的总和为5。

7
1 2 3 4 5 6 7

16 12