Best circular route profit

Problem

A college shuttle runs on a ring road with n stops, numbered 1 to n. After stop n comes stop 1 again. At each stop the shuttle gains or loses some rupees: ticket money minus tolls and fuel.

The transport team can run one trip that starts at any stop and visits one or more consecutive stops in order, each stop at most once. A trip may pass stop n and continue from stop 1. Print the largest total the trip can earn. The trip must visit at least one stop, even if every stop loses money.

Input, output and limits

Input: The first line has one integer n. The second line has n integers: the gain at each stop, from stop 1 to stop n. A loss is a negative number.
Output: One integer: the largest total of one trip.
Constraints: 1 ≤ n ≤ 10^5
-10^9 ≤ gain ≤ 10^9

Examples

Example 1

Input

5
5 -3 -6 2 5

Output

Start at stop 4 and go round to stop 1: 2 + 5 + 5 = 12.

Example 2

Input

3
-3 -2 -5

Output

-2

Every stop loses money. The best trip is the single stop with -2.

Hints

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

Hint 1

First solve it without the wrap: the best total of a straight run of consecutive stops.

Hint 2

For a straight run, keep the best total of a run that ends at the current stop: either start fresh here or extend the previous run.

Hint 3

A trip that wraps around leaves out a straight run in the middle. To make the wrapped trip as large as possible, leave out the run with the smallest total.

Hint 4

The answer is the larger of the best straight run and (total of all stops minus the smallest straight run). When every stop is a loss, the second value means visiting no stop, so use only the first.

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

Solve in the editor

All Java problems

Problem

Input, output and limits

Examples

Hints

More Array & String problems

Problem

Input, output and limits

Examples

Hints

More Array & String problems