题目描述

Farmer John 发明了一种饲养奶牛的新方法。他把 $N$ 捆干草排成一长排，方便地编号为 $1 \dots N$。第 $i$ 捆干草的重量为 $W_i$。一组六捆干草的重量可能如下所示：

Bessie 和 Dessie 事先知道所有干草的重量，并一起从左向右走过那一长排干草捆。她们轮流边走边挑选干草吃，Bessie 先手挑选（一旦跳过一捆干草，就不能再返回去拿它）。对于上面的例子，如果 Bessie 和 Dessie 沿着线走下去，一种可能的情况是：

• Bessie 选择重量为 $17$ 的那捆干草
• Dessie 跳过重量为 $5$ 的那捆，选择重量为 $9$ 的那捆
• Bessie 选择重量为 $10$ 的那捆
• Dessie 跳过重量为 $3$ 的那捆，选择重量为 $8$ 的那捆

图示如下：

Bessie   |      |
        17 5 9 10 3 8 
Dessie       |      |

这个演示的例子只展示了跳过一捆干草的情况；任何一头奶牛在自己的回合中都可以跳过任意数量的干草。

每头奶牛都希望最大化自己吃到的干草总重量（并且每头奶牛都知道对方也有这个目标）。此外，奶牛会选择 第一捆（即最靠右的） 能最大化她自己总重量的干草来吃。

给定一些干草捆的重量，请确定这对奶牛沿着干草捆长排走过时会吃到的干草数量。

输入格式

• 第一行：一个整数 $N$
• 接下来 $N$ 行：第 $i+1$ 行包含一个整数 $W_i$

输出格式

一行：两个空格分隔的整数，分别表示 Bessie 和 Dessie 吃到的干草总重量

6 
17 
5 
9 
10 
3 
8 

27 17 

提示

对于 $100\%$ 的数据：

• $1 \le N \le 7\times10^5$
• $1 \le W_i \le 2\times10^9$