Maximum Rings Collected

Sonic is dashing through a series of segments, each containing a certain number of rings. His goal is to collect as many rings as possible by running through a contiguous sequence of segments. Formally, given an array of integers representing the number of rings in each segment, you are to compute

$$\max_{1 \le i \le j \le n} \sum_{k=i}^{j} rings[k]$$

where n is the total number of segments. Even though all the segments in the test cases are positive, your solution should correctly implement an algorithm that would work in general (i.e. using Kadane's algorithm). Input is provided from standard input, and output must be printed to standard output.

inputFormat

The first line contains a single integer n representing the number of segments. The second line contains n space-separated integers, where the i-th integer represents the number of rings in the i-th segment.

outputFormat

Print a single integer which is the maximum number of rings that can be collected from a contiguous segment of the track.

## sample

1
5

5

</p>