← 返回题目列表

Codeforces · 381/A

A. 塞雷贾和迪玛

中文机器翻译题面 查看原题

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。