Maximum Subarray Sum

Given an array of n integers, your task is to find the contiguous subarray (containing at least one number) which has the largest sum and output its sum.

You may use Kadane's algorithm to solve this problem in O(n) time. The problem can be formulated as finding the maximum value of the sum: $$\max_{0 \leq i \leq j < n} \sum_{k=i}^{j} a_k$$ where \(a_k\) denotes the k-th element of the array.

Read the input from stdin and write the result to stdout.

inputFormat

The input begins with an integer n representing the number of elements in the array. The next line contains n space-separated integers representing the elements of the array.

Example:

9
-2 1 -3 4 -1 2 1 -5 4

outputFormat

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

Example:

6

## sample

9
-2 1 -3 4 -1 2 1 -5 4

6