Background

You are playing a physics line-drawing game.

Problem Description

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$.

2. 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.

Input Format

The first line contains an integer $N$.

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

Output Format

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.

6
6 10 -7 2 5 -12

19
56

Hint

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