A solar array logs the net energy gain (which may be negative on cloudy days) for each of n consecutive days. An operator wants the largest total that any single uninterrupted run of days could have produced.

Find the maximum sum over all non-empty contiguous runs of the sequence. If every day is a net loss, the answer is the single least-negative day (a run must contain at least one day). The intended approach splits the days in half and combines the best run in the left half, the best run in the right half, and the best run that straddles the midpoint.

Input format

Line 1: an integer n, the number of days. Line 2: n space-separated integers, the daily net gains.

Output format

A single integer: the maximum contiguous run sum.

Constraints

• 1 <= n <= 100000
• -1000000000 <= each gain <= 1000000000

9
-2 1 -3 4 -1 2 1 -5 4

6

3
-5 -2 -8

-2