P8067 [BalkanOI 2012] balls

You are playing a physics line-drawing game.

There are $N$ balls and $N$ cups, numbered from left to right as $1\dots N$. Initially, ball $i$ is aimed at cup $i$ (if nothing affects it, ball $i$ will fall into cup $i$). Cup $i$ has a score $c_i$. When a ball falls into a cup, you gain that cup’s score (cup capacity is considered infinite). Scores can be negative. You can draw two types of lines. Both endpoints of a line must be aimed at some cups, and the two endpoints cannot be the same cup. 1. From upper-left to lower-right. Let the cup aimed at by the upper-left endpoint be $i$, and the cup aimed at by the lower-right endpoint be $j$. Then all balls with indices $i\dots j$ will fall into cup $j$. 1. From upper-right to lower-left. Let the cup aimed at by the lower-left endpoint be $i$, and the cup aimed at by the upper-right endpoint be $j$. Then all balls with indices $i\dots j$ will fall into cup $i$. Now you want to know the maximum score you can get using **exactly one** line of the first type, and the maximum score you can get using **exactly one** line of the second type, respectively.

The first line contains an integer $N$. The next line contains $N$ integers, denoting $c_1\dots c_N$.

Output one integer on the first line: the maximum score when using only the first type of line. Output one integer on the second line: the maximum score when using only the second type of line.

#### Constraints Subtask #0 is the sample. $3\le N\le3\times10^5$, $|c_i|\le10^9$. #### Sample Explanation  The first picture shows the first type of line. Score: $6+10+5+5+5+(-12)=19$, and it can be proven to be the maximum. The second picture shows the second type of line. Score: $6+10+10+10+10+10=56$, and it can be proven to be the maximum. Translated by ChatGPT 5