Maximum Subarray Sum

You are given an array of n integers. Your task is to find the maximum sum of any contiguous subarray. In other words, find the maximum sum for any subarray A[i]...A[j] where 0 ≤ i ≤ j < n.

This problem can be solved efficiently using Kadane's Algorithm. The algorithm maintains a variable max_current which is updated using the formula:

[ max_current = \max(a_i, max_current + a_i) ]

and keeps track of the global maximum using:

[ max_global = \max(max_global, max_current) ]

</p>

Compute and output the maximum contiguous subarray sum.

inputFormat

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

outputFormat

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

## sample

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

6