题目描述

Alice and Bob bought a big persimmon, cut it into $n$ pieces with sizes $w_1, \dots, w_n$, and immediately started eating it. The kids will eat the pieces simultaneously, and for each of them, the eating process is as follows:

As soon as someone finishes eating their previous piece (and at the beginning of the meal), they choose the next piece and start eating it. If a piece of size $w$ is taken, it will take exactly $w$ seconds to eat it, and then it will be time to choose a new piece. If both finish eating their previous piece at the same time (or if the eating just started), Alice will choose the first piece, but they will start eating at the same time. Choosing a new piece does not take time.

Since both Alice and Bob are perfectionists, when they choose a piece, they will take either the smallest (with the smallest $w_i$) or the largest (with the largest $w_i$) from all the remaining pieces.

The eating process ends when the last person finishes eating and there are no more pieces left.

Both Alice and Bob are interested in eating as much as possible. Find the total size of the pieces that Alice will eat and the total size of the pieces that Bob will eat, if they both choose the pieces optimally.

输入格式

The first line contains a single integer $n$ $(1 \le n \le 2000)$ --- the number of persimmon pieces.

The second line contains $n$ integers $w_1,\ w_2,\ \dots,\ w_n$ ($1 \le w_i \le 20\,000$, $w_i \le w_{i + 1}$) --- the sizes of the persimmon pieces.

Let $W$ denote the sum of the sizes of all the pieces. It is guaranteed that $W \le 20\,000$.

输出格式

In a single line, output two numbers --- the total size of the pieces that Alice will eat and the total size of the pieces that Bob will eat, if they both choose the pieces optimally.

5
1 1 3 4 6

8 7

4
1 1 2 2

3 3

4
1 7 7 9

10 14

提示

Note

In the first example, Alice should first take a piece of size $1$. Immediately after that, Bob should also take a piece of size $1$. After a second, Alice will take a piece of size $3$, and then Bob will take a piece of size $6$. $3$ seconds later, Alice will take a piece of size $4$. $3$ seconds later, Bob will finish eating, and a second later the process will finish. At this point, Alice will eat pieces of sizes $1 + 3 + 4 = 8$, and Bob: $1 + 6 = 7$.

In the third example, Alice should take a piece of size $1$, and Bob should take a piece of size $7$. After a second, Alice will take a piece of size $9$, and $6$ seconds later, Bob will take a piece of size $7$.

Scoring

The tests for this problem consist of four groups. Points for each group are given only if all tests of the group and all tests of the required groups are passed.. Note that passing the example tests is not required for some groups. $\textbf{Offline-evaluation}$ means that the results of testing your solution on this group will only be available after the competition.

Group	Points	Additional constraints	<	Required Groups	Comment
		$n$	$w_i$
0		--	--	--	Examples.
1	10	$n = 3$			--
2	12	--	$w_i \le 2$
3	19	$n \le 200$	$w_i \le 500$	0
4	15	$n \le 500$	$W \le 5000$	--	$w_{i+1} \le 2 \cdot w_i$ for all $1 \le i \le n - 1$
5	13	--		2, 4
6	31			0 -- 5	Offline-evaluation.