题目描述

有 $N$ 个盒子从左到右排成一排。第 $i$ 个盒子中有 $a_i$ 个馒头（内有豆沙馅的馒头）。Sugim 和 Sigma 用这些盒子玩一个游戏。他们轮流进行如下操作。Sugim 先手，游戏在总共进行了 $N$ 次操作后结束。

• 选择一个仍未被放置棋子的盒子，并且该盒子与对方在上一次操作中选择的盒子相邻，然后在该盒子中放入自己的棋子。如果存在多个满足条件的盒子，可以任选其中之一。
• 如果不存在满足条件的盒子，或者这是 Sugim 的第一次操作，则可以选择任意一个尚未放置棋子的盒子，并在其中放一枚棋子。

游戏结束时，每位玩家可以获得自己所下棋子的格子中的所有馒头。他们都非常喜欢馒头，并且足够聪明，都会采取最优策略，以使自己最终获得的馒头数量最大。

请你求出最终 Sugim 和 Sigma 各自能获得多少个馒头。

输入格式

输入按以下格式从标准输入中给出：

$N$ $a_1$ $a_2$ $\dots$ $a_N$

输出格式

输出 Sugim 和 Sigma 各自最终获得的馒头数，中间用空格隔开。

样例 1

输入

5
20 100 10 1 10

输出

120 21

样例 2

输入

6
4 5 1 1 4 5

输出

11 9

样例 3

输入

5
1 10 100 10 1

输出

102 20

说明/提示

样例解释 1

若双方都选择最优策略，游戏过程如下：

• 首先，Sugim 必须把棋子放在第二个盒子。
• 然后，Sigma 必须把棋子放在最左边的盒子。
• 然后，Sugim 把棋子放在第三个或第五个盒子。
• 接着，Sigma 把棋子放在第四个盒子。
• 最后，Sugim 把棋子放在剩下的盒子里。

数据范围

• $2 \leq N \leq 300\,000$
• $1 \leq a_i \leq 1000$
• 输入保证所有数值均为整数。

由 ChatGPT 5 翻译