Maximum Subarray Sum

You are given an array of integers. Your task is to find the maximum sum of any contiguous subarray within the array. If the array is empty, the result should be 0.

This problem can be solved efficiently using Kadane's algorithm. In mathematical terms, if the array is \(a_1, a_2, \dots, a_n\), you need to find \[ \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \] with the special case that if \(n=0\) then the answer is 0.

inputFormat

The input is given from stdin in the following format:

n
a1 a2 ... an

where n is a non-negative integer representing the number of elements in the array. If n = 0, then the array is empty.

outputFormat

Output a single integer to stdout representing the maximum sum of any contiguous subarray. For an empty array, output 0.

## sample

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

6

</p>