Optimal Cake Division Game

Bessie and Elsie have discovered a row of (N) cakes, where (N) is an even integer satisfying (2\le N\le 5\cdot10^5), and the sizes of the cakes are given by (a_1,a_2,\dots,a_N) with (1\le a_i\le 10^9). The two cows want to eat as much cake as possible. However, being very courteous, they agree to play the following game to divide the cakes. The game proceeds in turns with Bessie moving first. On each turn, one of the following actions is taken:

1. On Bessie’s turn she chooses any two adjacent cakes and stacks them, forming a new cake whose size is the sum of the two cakes. (That is, if she stacks cakes of sizes (x) and (y), the new cake has size (x+y).)
2. On Elsie’s turn she chooses to hide either the leftmost or the rightmost cake (removing it from the row).

The game ends when only one cake remains. At that point, Bessie eats the final (merged) cake, and Elsie eats all the cakes she has hidden. Both players play optimally to maximize the amount of cake they end up eating. Under optimal play, determine the final amount of cake (in total size) that Bessie consumes and the final amount that Elsie consumes.

A key observation is that the game is zero–sum: the total cake size (S=\sum_{i=1}^{N}a_i) is divided between the two cows. Bessie’s moves only merge adjacent cakes without changing the total cake in that contiguous block, while Elsie’s removals subtract from the final cake Bessie will eventually eat. In fact, it can be shown that no matter how Bessie chooses to merge, the final remaining cake is the merge (i.e. the sum) of a contiguous block of the original cakes. Since Elsie gets to choose (by removing one cake per her turn) which of the possible contiguous blocks remains, she will force the outcome that minimizes Bessie’s share. In particular, let (N=2k) (so that (k\ge 1)). Elsie makes exactly (k-1) moves, and the final cake will be the merge of (k+1) original cakes. The only possible contiguous blocks that can remain are (a_{i+1}+a_{i+2}+\cdots+a_{i+k+1}) for (i=0,1,\dots,k-1) (using 0-based indexing to describe positions). Under optimal play, Elsie will force the block with the minimum sum among these.

Thus, if we define [ F = \min_{0 \le i \le k-1}\Bigl(\sum_{j=i+1}^{i+k+1} a_j\Bigr), ] then Bessie’s final cake has size (F) and Elsie’s total is (S-F).

inputFormat

The first line contains an even integer \(N\) (\(2\le N\le 5\cdot10^5\)).
The second line contains \(N\) space-separated integers \(a_1,a_2,\dots,a_N\) (\(1\le a_i \le 10^9\)).

outputFormat

Output two space‐separated integers: the total cake size that Bessie consumes and the total cake size that Elsie consumes under optimal play.

sample

2
1 2

3 0