Maximum Subarray Sum

Given an array of integers, your task is to find the contiguous subarray which has the largest sum and then output that sum. This problem can be mathematically formulated as:

where (a_1, a_2, \dots, a_n) are the elements of the array. An efficient solution to this problem is provided by Kadane's algorithm, which runs in linear time.

inputFormat

The first line of input contains a single integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers, which are the elements of the array.

outputFormat

Output a single integer, the maximum sum of any contiguous subarray.## sample

5
-1 2 3 -2 5

8