Maximum Subarray Sum

Given a list of integers, your task is to find the maximum possible sum of any contiguous subarray. In other words, for an array (a_1, a_2, \dots, a_n), you need to compute the maximum value of (S = \sum_{k=i}^{j}a_k) for (1 \leq i \leq j \leq n). This is a classical problem that can be efficiently solved using Kadane's algorithm.

inputFormat

Input is read from standard input. The first line contains an integer (n) which is the number of elements in the array. The second line contains (n) space-separated integers representing the elements of the array.

outputFormat

Output the maximum sum of any contiguous subarray. The answer is printed to standard output.## sample

5
1 -2 3 4 -1

7