爱丽丝（Alice）和鲍勃（Bob）买了一个大柿子，将其切成 $n$ 块，大小分别为 $w_1, \dots, w_n$，并立即开始吃。孩子们会同时吃这些柿子，对他们每个人来说，吃的过程如下：

一旦有人吃完上一块（以及在刚开始吃的时候），他们就会选择下一块并开始吃。如果拿了一块大小为 $w$ 的柿子，需要恰好 $w$ 秒才能吃完，然后就到了选择新一块的时候。如果两人同时吃完上一块（或者刚开始吃的时候），爱丽丝将先选择，但他们会同时开始吃。选择新的一块不需要时间。

由于爱丽丝和鲍勃都是完美主义者，当他们选择一块时，他们只会从所有剩余的块中选择最小的（$w_i$ 最小）或最大的（$w_i$ 最大）一块。

当最后一个人吃完且没有剩余的块时，吃的过程结束。

爱丽丝和鲍勃都希望自己吃到的总量尽可能多。如果他们都采取最优策略来选择，求爱丽丝吃到的柿子总大小和鲍勃吃到的柿子总大小。

输入格式

第一行包含一个整数 $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$。

输出格式

在一行中输出两个数 —— 如果两人都采取最优策略，爱丽丝吃到的柿子总大小和鲍勃吃到的柿子总大小。

样例

输入样例 1

5
1 1 3 4 6

输出样例 1

8 7

输入样例 2

4
1 1 2 2

输出样例 2

3 3

输入样例 3

4
1 7 7 9

输出样例 3

10 14

说明

在第一个样例中，爱丽丝应该首先拿一块大小为 $1$ 的。紧接着，鲍勃也应该拿一块大小为 $1$ 的。$1$ 秒后，爱丽丝将拿一块大小为 $3$ 的，然后鲍勃将拿一块大小为 $6$ 的。$3$ 秒后，爱丽丝将拿一块大小为 $4$ 的。再过 $3$ 秒，鲍勃将吃完，又过 $1$ 秒后整个过程结束。此时，爱丽丝吃到的块大小为 $1 + 3 + 4 = 8$，鲍勃吃到的为 $1 + 6 = 7$。

在第三个样例中，爱丽丝应该拿一块大小为 $1$ 的，鲍勃应该拿一块大小为 $7$ 的。$1$ 秒后，爱丽丝将拿一块大小为 $9$ 的，再过 $6$ 秒后，鲍勃将拿一块大小为 $9$ 的。

子任务

本题的测试点分为若干个子任务。只有当通过该子任务的所有测试点以及所有依赖子任务的测试点时，才能获得该子任务的分数。请注意，某些子任务不需要通过样例测试。非正式评测（Offline-evaluation）意味着该子任务的评测结果仅在比赛结束后公布。