P2975 [USACO10JAN] Taking Turns G

Farmer John 发明了一种饲养奶牛的新方法。他把 $N$ 捆干草排成一长排，方便地编号为 $1 \dots N$。第 $i$ 捆干草的重量为 $W_i$。一组六捆干草的重量可能如下所示： $$ 17 \quad 5 \quad 9 \quad 10 \quad 3 \quad 8 $$ Bessie 和 Dessie 事先知道所有干草的重量，并一起从左向右走过那一长排干草捆。她们轮流边走边挑选干草吃，Bessie 先手挑选（一旦跳过一捆干草，就不能再返回去拿它）。对于上面的例子，如果 Bessie 和 Dessie 沿着线走下去，一种可能的情况是： - Bessie 选择重量为 $17$ 的那捆干草 - Dessie 跳过重量为 $5$ 的那捆，选择重量为 $9$ 的那捆 - Bessie 选择重量为 $10$ 的那捆 - Dessie 跳过重量为 $3$ 的那捆，选择重量为 $8$ 的那捆 图示如下： ```plain Bessie | | 17 5 9 10 3 8 Dessie | | ``` 这个演示的例子只展示了跳过一捆干草的情况；任何一头奶牛在自己的回合中都可以跳过任意数量的干草。 每头奶牛都希望最大化自己吃到的干草总重量（并且每头奶牛都知道对方也有这个目标）。此外，奶牛会选择 **第一捆（即最靠右的）** 能最大化她自己总重量的干草来吃。 给定一些干草捆的重量，请确定这对奶牛沿着干草捆长排走过时会吃到的干草数量。

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

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

对于 $100\%$ 的数据： - $1 \le N \le 7\times10^5$ - $1 \le W_i \le 2\times10^9$