卡片游戏

Sereja 和 Dima 玩一个游戏。游戏规则非常简单：玩家们有 \(n\) 张卡片排成一行。每张卡片上都有一个数字，所有卡片上的数字都是不同的。玩家轮流出手，Sereja 先出。在他的回合，玩家可以拿走一张卡片：要么是最左边的卡片，要么是最右边的卡片。当没有卡片可取时，游戏结束。游戏结束时，拥有卡片上数字之和最大的一方获胜。
Sereja 和 Dima 都很贪心，每个人在自己的回合选择数字较大的卡片。 Inna 是 Sereja 和 Dima 的朋友，她知道他们的策略，因此她希望根据游戏的初始状态来确定最后的分数。请帮她解决这个问题。

输入

第一行包含一个整数 \(n\) (\(1 \le n \le 1000\))——桌面上的卡片数量。
第二行包含从左到右的卡片上的数字，数字是空格分隔的。卡片上的数字是 \(1\) 到 \(1000\) 之间的不同整数。

输出

输出一行，包含两个整数，第一个是 Sereja 在游戏结束时的得分，第二个是 Dima 在游戏结束时的得分。

输入：

4
4 1 2 10

输出：

12 5

输入：

7
1 2 3 4 5 6 7

输出：

16 12

说明

在第一个示例中，Sereja 会选择数字 \(10\) 和 \(2\)，所以 Sereja 的总分是 \(12\)。Dima 会选择数字 \(4\) 和 \(1\)，所以 Dima 的总分是 \(5\)。