CF859C.Pie Rules

You may have heard of the pie rule before. It states that if two people wish to fairly share a slice of pie, one person should cut the slice in half, and the other person should choose who gets which slice. Alice and Bob have many slices of pie, and rather than cutting the slices in half, each individual slice will be eaten by just one person.

The way Alice and Bob decide who eats each slice is as follows. First, the order in which the pies are to be handed out is decided. There is a special token called the "decider" token, initially held by Bob. Until all the pie is handed out, whoever has the decider token will give the next slice of pie to one of the participants, and the decider token to the other participant. They continue until no slices of pie are left.

All of the slices are of excellent quality, so each participant obviously wants to maximize the total amount of pie they get to eat. Assuming both players make their decisions optimally, how much pie will each participant receive?

你可能以前听说过“分饼规则”（pie rule）。该规则指出：若两人希望公平地分享一块饼，其中一人应将这块饼切成两半，另一人则选择自己拿哪一半。而爱丽丝（Alice）和鲍勃（Bob）有很多块饼，但他们并不将每一块饼切成两半，而是每一块饼仅由其中一人独自吃完。

爱丽丝和鲍勃决定每一块饼由谁来吃的方式如下：首先确定饼被分发的顺序。存在一个特殊的标记物，称为“决策者”（decider）标记，初始时由鲍勃持有。在所有饼都被分发完毕之前，持有“决策者”标记的人将把下一块饼分配给两名参与者中的某一位，并将“决策者”标记交给另一位参与者。此过程持续进行，直至所有饼均被分发完毕。

所有饼的质量都极佳，因此每位参与者显然都希望最大化自己所吃到的饼的总量。假设双方均以最优策略进行决策，那么每位参与者最终将各获得多少饼？

Input will begin with an integer N (1 ≤ N ≤ 50), the number of slices of pie.

Following this is a line with N integers indicating the sizes of the slices (each between 1 and 100000, inclusive), in the order in which they must be handed out.

输入的第一行是一个整数 $N$（$1 \leq N \leq 50$），表示派的块数。

接下来的一行包含 $N$ 个整数，表示各块派的大小（每个大小在 $1$ 到 $100000$ 之间，含端点），按必须分发的顺序给出。

Print two integers. First, the sum of the sizes of slices eaten by Alice, then the sum of the sizes of the slices eaten by Bob, assuming both players make their decisions optimally.

输出两个整数：第一个是爱丽丝所吃披萨片尺寸之和，第二个是鲍勃所吃披萨片尺寸之和（假设双方均采取最优策略）。

In the first example, Bob takes the size 141 slice for himself and gives the decider token to Alice. Then Alice gives the size 592 slice to Bob and keeps the decider token for herself, so that she can then give the size 653 slice to herself.

在第一个例子中，鲍勃为自己取走大小为 141 的蛋糕块，并将决策权令牌交给爱丽丝。随后，爱丽丝将大小为 592 的蛋糕块给鲍勃，并为自己保留决策权令牌，以便她接下来可以将大小为 653 的蛋糕块分给自己。