Balls

Time limit1sMemory limit128 MB

Summary

There are n balls and n holes. Balls fall straight down from (i,h) to holes at (i,0). Placing exactly one obstacle (a segment between two integer columns) that tilts right redirects all balls in its column range to its right (lower) end; tilting left redirects them to its left (lower) end. For each orientation, maximize the total score over all valid placements (both orientations must be used, i.e., one obstacle of the specified tilt is mandatory, even if it reduces the total). Constraints n up to 3e5, c_i up to 1e9 in absolute value, so O(n log n) or O(n) required, answers in 64-bit.

Level: Medium5 of 10
Topics: Array, Prefix sum, Greedy, Math
Solved: No attempts yet

Problem

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?

Input

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.

Output

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.

Constraints

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

Note

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.

Examples1

Example 1
Input
```
6
6 10 -7 2 5 -12
```
Expected output
```
19
56
```