Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of any contiguous subarray.

This problem is efficiently solved by Kadane's algorithm. The algorithm is based on the following recurrence:

\( current\_max = \max(a_i, current\_max + a_i) \) and \( max\_so\_far = \max(max\_so\_far, current\_max) \).

Input and output are taken from standard input and output respectively.

inputFormat

The first line of input contains an integer n representing the number of elements in the array.

The second line contains n space-separated integers.

outputFormat

Output a single integer, which is the maximum subarray sum.

## sample

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

6

</p>