题目描述

Sereja 和 Dima 玩一个游戏。游戏规则非常简单：他们有 $n$ 张牌排成一行，每张牌上写着一个数字，所有牌上的数字互不相同。两名玩家轮流行动，Sereja 先手。在自己的回合中，玩家可以从当前牌堆的最左端或最右端取走一个牌。所有牌都被取光时，游戏结束。拥有手中牌面数字总和最大的玩家获胜。

Sereja 和 Dima 都非常贪心：每次轮到自己时，他们都会选择当前更大的那一张牌。

Inna 是 Sereja 和 Dima 的朋友。她知道两位玩家的策略，现在想预测最终的得分情况。请帮助她计算给定初始牌面状态下，最终的分数。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 1000$）——牌的数量。
第二行包含 $n$ 个用空格隔开的整数，分别表示从左到右每张牌上的数字。牌上的数字互不相同，且都是 $1$ 到 $1000$ 之间的整数。

输出格式

在一行输出两个整数，分别表示游戏结束时 Sereja 和 Dima 的得分。

说明/提示

在第一个样例中，Sereja 会取走数字为 $10$ 和 $2$ 的牌，得分为 $12$。Dima 会取走数字为 $4$ 和 $1$ 的牌，得分为 $5$。

由 ChatGPT 5 翻译

样例

4
4 1 2 10

12 5

7
1 2 3 4 5 6 7

16 12