Sereja 和 Dima 在玩一个游戏。桌上有 $n$ 张牌排成一行，每张牌上写着一个数，且所有数两两不同。两人轮流取牌，Sereja 先手。每次轮到某位玩家时，他可以从牌列中取走 最左边 或 最右边 的一张牌。直到所有牌都被取走，游戏结束。最终，手中牌面数字之和更大的玩家获胜。

Sereja 和 Dima 都很贪心：每次都从左右两端可选的两张牌中选择数字更大的一张（若左端更大取左端，否则取右端）。

给定初始牌列，请输出两人最终各自的得分。

输入格式

• 第一行一个整数 $n$（$1 \le n \le 1000$），表示牌的数量。
• 第二行 $n$ 个整数，从左到右表示牌面数字。所有数字互不相同，且都在 $[1,1000]$ 范围内。

输出格式

输出一行两个整数： 第一个为 Sereja 的最终得分，第二个为 Dima 的最终得分。

样例 1

输入

4
4 1 2 10

输出

12 5

样例 2

输入

7
1 2 3 4 5 6 7

输出

16 12