Description

There is a sequence $a$ of length $n$. Two players take turns. Each time, a player may choose a number that is adjacent to $0$, gain a score equal to its value, and change it to $0$. Find the scores of the two players if both play optimally.

Input Format

The first line contains an integer $n$, as described in the statement.

The next line contains $n$ integers, representing the sequence.

Output Format

Output one line with two integers, representing the final scores of the two players when both play optimally.

8
1 2 0 3 7 4 0 9

17 9

Hint

Constraints

For all testdata, it is guaranteed that $1\leq n\leq 10^6$. For any element $x$ in $a$, it is guaranteed that $0\leq x\leq 10^6$, and there is at least one $0$.

Translated by ChatGPT 5