Balls

There are $n$ balls and $n$ holes on a standard coordinate plane. The balls sit at positions $(1, h), (2, h), \dots, (n, h)$ for some height $h > 0$, and the holes are at $(1, 0), (2, 0), \dots, (n, 0)$. All balls are released at the same instant and fall straight down (in the negative $y$ direction). If a ball lands in the $i$-th hole you earn $c_i$ points.

If nothing is done, ball $i$ falls into hole $i$ and the total is $c_1 + c_2 + \dots + c_n$. To change the result you must place exactly one obstacle, which is a straight segment joining two integer columns:

• A right obstacle joins $(x_1, y_1)$ and $(x_2, y_2)$ with $x_1, x_2 \in \mathbb{N}$, $1 \le x_1 < x_2 \le n$ and $h > y_1 > y_2 > 0$ (it tilts down to the right, so its right end is the lower end).
• A left obstacle joins $(x_1, y_1)$ and $(x_2, y_2)$ with $x_1, x_2 \in \mathbb{N}$, $1 \le x_1 < x_2 \le n$ and $0 < y_1 < y_2 < h$ (it tilts down to the left, so its left end is the lower end).

When a falling ball touches the segment it stops, slides down to the lower end of the segment, and then drops straight into the hole directly beneath that lower end. Every ball whose column lies in the range $[x_1, x_2]$ is caught. Hence a right obstacle sends balls $x_1, x_1 + 1, \dots, x_2$ all into hole $x_2$, and a left obstacle sends balls $x_1, x_1 + 1, \dots, x_2$ all into hole $x_1$. After the obstacle is placed some holes may hold several balls and others none, but every ball still ends up in some hole.

Answer the following two questions:

• What is the highest score you can achieve if you must place exactly one right obstacle?
• What is the highest score you can achieve if you must place exactly one left obstacle?

The first line contains one integer $n$ — the number of balls (which equals the number of holes). The second line contains $n$ space-separated integers $c_1, c_2, \dots, c_n$ — the values of the holes, listed from left to right.

Print two lines. On the first line print a single integer: the highest achievable score when you must place exactly one right obstacle. On the second line print a single integer: the highest achievable score when you must place exactly one left obstacle. The answers can fall outside the 32-bit range, so use a 64-bit integer type.

• $3 \le n \le 300,000$.
• $-10^9 \le c_i \le 10^9$.

Consider the sample with $c = [6, 10, -7, 2, 5, -12]$. The best right obstacle catches balls 3, 4, and 5 and drops them into hole 5, giving $6 + 10 + 5 + 5 + 5 + (-12) = 19$. The best left obstacle catches balls 2 through 6 and drops them into hole 2, giving $6 + 10 + 10 + 10 + 10 + 10 = 56$. No other placement scores higher. Because an obstacle is mandatory, the required segment can lower the total when every possible placement is unfavorable.