beecrowd | 2917

String

By Anderson Franz, UNOCHAPECÓ BR Brazil

Timelimit: 2

Joao and Cleobaldo cut a white string with M meters and traced a line from left to right int it. For every 10 centimeters of the string was pasted a number and the two would like to know what would be the largest continuous sum between the numbers pasted on the string. This answer could be greater if instead of a straight was a circle, they agreed that they will pick up the end of the string on the right side and make a knot with the left end of the string, now this string is no longer a straight line, and now they want to know what is the maximum continuous sum between the elements. All that is known is that you can use maximum numbers (M * 10) continuous numbers written on the string and get the maximum sum, can you help them. After they joined the ends of the string the leftmost element is now a continuous element of the element that was to the right.

Input

The input has several test cases and ends with EOF. In the first line there is an integer M which represents respectively the number of meters of the string, M <= 105, followed by M * 10 integers MI, which will be glued to the string, following the order from left to right.-105 < MI <= 105.

Output

The output represents respectively the maximum continuous sum as described above. The sum will always be greater than 0 and less than 107.

Input Sample Output Sample

1

1 2 3 4 5 -6 -7 -8 -9 1

2

10 2 2 1 2 2 2 -4 -5 -6 -7 -8 23 24 -5 -6 -3 -2 -2 11

16

61