Best stretch of marks

Problem

A list of daily gains and losses is given. Print the largest sum of any non-empty run of neighbouring days. All days may be losses, and then the answer is the least bad single day. The starter holds a program with a bug. Find it and fix it.

Input, output and limits

Input: Line 1: n. Line 2: n integers.
Output: One integer: the largest sum of a non-empty run.
Constraints: 1 ≤ n ≤ 100000
-1000 ≤ each value ≤ 1000

Examples

Example

Input

5
-2 3 -1 4 -6

Output

The run 3 -1 4 adds up to 6.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Track the best sum of a run that ends at the current day.

Hint 2

That run either starts again at this day or extends the one before it.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Find each valuemedium
Pairs with a given sumhard
Balanced bracketsmedium
Longest run of equal valueshard
Rotate right by kmedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Testing Your Solutions problems

Problem

Input, output and limits

Examples

Hints

More Testing Your Solutions problems