Description

Company A is hosting a two-player puzzle contest — the stone-taking game. The winner will receive a generous prize provided by Company A, attracting many clever contestants from all over the country.

Compared with the classic stone-taking game, the rules of this contest are much more complex:

• There are $N$ piles of stones arranged in a row. The $i$-th pile contains $a_i$ stones.
• Some piles have already been deliberately removed by Company A at the start.
• The two players then take turns. On each turn, a player may take all the stones from exactly one pile, subject to the following constraint: to take a pile, at least one of its adjacent piles must have already been taken (either previously by a player or initially removed by Company A). Note: pile $1$ is adjacent only to pile $2$, pile $N$ is adjacent only to pile $N-1$, and any other pile $i$ is adjacent to piles $i-1$ and $i+1$.
• The game ends when all stones have been taken. The player who has collected more stones in total wins.

As one of the contestants, you want to know, for any game, if both the first player and the second player play optimally, what total number of stones each will obtain.

Input Format

The first line contains a positive integer $N$, the number of piles. The second line contains $N$ space-separated nonnegative integers $a_1, a_2, \ldots, a_N$, where $a_i$ is the number of stones in the $i$-th pile, and $a_i = 0$ means the $i$-th pile was initially removed by Company A. The input guarantees $0 \le a_i \le 10^8$, and there exists at least one $i$ such that $a_i = 0$.

Output Format

Output a single line containing two integers: the total stones obtained by the first player and by the second player under optimal play, separated by a single space.

8
1 2 0 3 7 4 0 9

17 9

Hint

Sample explanation: when both players play optimally, the piles are taken in the order $9, 2, 1, 4, 7, 3$, so the first player gets $9 + 1 + 7 = 17$ stones and the second player gets $2 + 4 + 3 = 9$ stones.

Constraints:

• For $30\%$ of the testdata, $2 \le N \le 100$.
• For $100\%$ of the testdata, $2 \le N \le 10^6$.

Translated by ChatGPT 5