Maximum Subarray Sum

You are given an array of n integers. Your task is to find the maximum sum of a contiguous subarray. This is a classic problem that can be efficiently solved using Kadane's Algorithm. In mathematical terms, given an array \(a_1, a_2, \dots, a_n\), you need to compute:

\[ \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \]

The subarray must contain at least one element.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains an integer n which represents the number of elements in the array.
2. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output the maximum sum of any contiguous subarray to stdout.

## sample

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

6

</p>