Description

Alice 和 Bob 买了一个大柿子，把它切成了 $n$ 块，每块的大小分别为 $w_1, \dots, w_n$，他们立刻开始吃起来。两个孩子会同时吃柿子，每个人的吃法如下：

每当某人吃完上一块（或刚开始时），他就会选择下一块开始吃。如果某块的大小为 $w$，那么吃掉它需要恰好 $w$ 秒，吃完后就可以选择新的一块。若两人同时吃完（或刚开始），则 Alice 先选第一块，但两人会同时开始吃。选择新的一块不需要时间。

由于 Alice 和 Bob 都是完美主义者，每次选块时，他们都只会从剩下的所有块中选最小的或最大的（即 $w_i$ 最小或最大的）。

吃的过程会一直持续到最后一人吃完且没有剩下的块为止。

Alice 和 Bob 都希望自己吃到的总量尽量多。请你求出，如果两人都采取最优策略，Alice 吃到的柿子总量和 Bob 吃到的柿子总量分别是多少。

Input Format

第一行一个整数 $n$（$1 \le n \le 2000$），表示柿子块的数量。

第二行 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le 20\,000$，$w_i \le w_{i+1}$），表示每块柿子的大小。

记 $W$ 为所有块的总大小，保证 $W \le 20\,000$。

Output Format

输出一行两个整数，分别表示 Alice 和 Bob 吃到的柿子总量（都采取最优策略时）。

5
1 1 3 4 6

8 7

4
1 1 2 2

3 3

4
1 7 7 9

10 14

Hint

说明

在第一个样例中，Alice 应该先选一块大小为 $1$ 的柿子，然后 Bob 也选一块大小为 $1$ 的柿子。一秒后，Alice 选 $3$，Bob 选 $6$。三秒后，Alice 选 $4$。又三秒后，Bob 吃完，Alice 再过一秒吃完。此时，Alice 吃的总量为 $1+3+4=8$，Bob 吃的总量为 $1+6=7$。

在第三个样例中，Alice 先选 $1$，Bob 选 $7$。一秒后，Alice 选 $9$，再过 $6$ 秒，Bob 选 $7$。

计分方式

本题共四组测试。只有通过该组及其所有依赖组全部测试，才能获得该组分数。部分组不要求通过样例测试。Offline-evaluation 表示该组结果仅在赛后可见。

翻译由 ChatGPT-4.1 完成。