[HNOI2010]取石头游戏

题目描述

A 公司正在举办一个智力双人游戏比赛 - 取石子游戏,游戏的获胜者将会获得 A 公司提供的丰厚奖金,因此吸引了来自全国各地的许多聪明的选手前来参加比赛。 与经典的取石子游戏相比,A 公司举办的这次比赛的取石子游戏规则复杂了很多: * 总共有 $N$ 堆石子依次排成一行,第 $i$ 堆石子有 $a_i$ 个石子。 * 开始若干堆石子已被 A 公司故意拿走。 * 然后两个玩家轮流来取石子,每次每个玩家可以取走一堆中的所有石子,但有一个限制条件:一个玩家若要取走一堆石子,则与这堆石子相邻的某堆石子已被取走(之前被某个玩家取走或开始被 A 公司故意拿走)。注意:第 $1$ 堆石子只与第 $2$ 堆石子相邻,第 $N$ 堆石子只与第 $N-1$ 堆石子相邻,其余的第 $i$ 堆石子与第 $i-1$ 堆和第 $i+1$ 堆石子相邻。 * 所有石子都被取走时,游戏结束。谁最后取得的总石子数最多,谁就获得了这场游戏的胜利。 作为这次比赛的参赛者之一,绝顶聪明的你,想知道对于任何一场比赛,如果先手者和后手者都使用最优的策略,最后先手者和后手者分别能够取得的总石子数分别是多少。

输入输出格式

输入格式


第一行是一个正整数 $N$,表示有多少堆石子。输入文件第二行是用空格隔开的 $N$ 个非负整数 $a_1, a_2,\ldots, a_N$,其中 $a_i$ 表示第 $i$ 堆石子有多少个石子,$a_i = 0$ 表示第 $i$ 堆石子开始被 A 公司故意拿走。输入的数据保证 $0\leq a_i\leq 10^8$,并且至少有一个 $i$ 使得 $a_i = 0$。

输出格式


仅包含一行,为两个整数,分别表示都使用最优策略时,最后先手者和后手者各自能够取得的总石子数,并且两个整数间用一个空格隔开。

输入输出样例

输入样例 #1

8
1 2 0 3 7 4 0 9

输出样例 #1

17 9

说明

样例解释:两个玩家都使用最优策略时取走石子的顺序依次为 $9, 2, 1, 4, 7, 3$,因此先手者取得 $9 + 1 + 7 = 17$ 个石子,后手者取得 $2 + 4 + 3 = 9$ 个石子。 $30\%$ 的数据满足 $2\leq N\leq 100$。 $100\%$ 的数据满足 $2\leq N\leq 10^6$。