Indian National Olympiad in Informatics

Related:

Online Programming Contest, 11-12 February 2006

IARCS home > OLYMPIAD

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