Maximum Continuous Subarray Sum

Given n integers in a row, find the maximum sum of a contiguous subarray. Note that at least one number must be chosen in forming the subarray.

You are to compute the value $$\max_{1 \le i \le j \le n}{\sum_{k=i}^{j}a_k},$$ where \(a_1, a_2, \ldots, a_n\) are the given integers.

inputFormat

The first line contains an integer n indicating the number of integers.

The second line contains n space-separated integers.

outputFormat

Output a single integer which is the maximum sum of any contiguous subarray.

sample

5
-2 1 -3 4 -1

4