Sereja 和 Dima 玩游戏。游戏规则非常简单。玩家连续有 n 张牌。每张卡片都包含一个数字,卡片上的所有数字都是不同的。球员们轮流行动,Sereja 首先行动。在轮到玩家时,他可以拿一张牌:要么是一排最左边的牌,要么是最右边的一张。当没有更多牌时游戏结束。游戏结束时,卡片上的数字总和最大的玩家获胜。
Sereja 和 Dima 很贪婪。他们每个人在移动过程中选择数字较大的牌。
Inna 是 Sereja 和 Dima 的朋友。她知道这些人正在使用哪种策略,因此她想根据游戏的初始状态确定最终得分。帮助她。
输入
第一行包含整数 n (1 ≤ n ≤ 1000) — 桌上的牌数。第二行包含卡片上从左到右以空格分隔的数字。卡片上的数字是 1 到 1000 之间的不同整数。
输出
在一行上打印两个整数。第一个数字是比赛结束时塞雷贾的得分,第二个数字是比赛结束时迪马的得分。
示例
输入 #1
4 4 1 2 10
输出 #1
12 5
输入 #2
7 1 2 3 4 5 6 7
输出 #2
16 12
注意
在第一个示例中,Sereja 将拿走数字 10 和 2 的牌,因此 Sereja 的总和为 12。Dima 将拿走数字 4 和 1 的牌,因此 Dima 的总和为 5。