### Indian National Olympiad in Informatics

### Online Programming Contest, 11-12 February 2006

### Basic Division

Problem 1: Zorgian Roulette, *(K Narayan Kumar, CMI)*

The inhabitants of Zorg have developed a strange version of
roulette. In their game, a list of numbers is written around a
circular dial. For example, the list could look like this:

2 -4 6 -1 -4 8 -1 3

Remeber that the list wraps around the disk, so the `3`
at the right end is followed by the `2` on the left end.

The aim of the game is to identify the maximum sum one can get by
adding up the numbers along some contiguous segment of the list. For
example, in the sequence above, the highest sum, 14, is attained in the
sequence `8 -1 3 2 -4 6`. Notice how this sequence winds
around the end of the list and back through the beginning, since the
numbers are written around a circular dial.

Input format

The first line of the input contains a single integer *N*
indicating the size of the list. The second line contains *N*
integers.

Output format

A single integer indicating the maximum sum among all segments of
the numbers in the input list, assuming they are written around a
circular dial.

Test data

You may assume that 1 ≤ *N* ≤ 300 in 40% of the
inputs. You may assume that 1 ≤ *N* ≤ 2000 in 90% of the
inputs. In all the inputs 1 ≤ *N* ≤ 100000.

Example

We now illustrate the input and output formats using the example
described above.

Sample input

8
2 -4 6 -1 -4 8 -1 3

Sample output

14