Maximum Subarray Sum

Given a sequence \(a\) of length \(n\), find a contiguous non-empty segment such that the sum of its elements is maximized.

You are required to output the maximum sum among all possible contiguous subarrays.

inputFormat

The input begins with an integer \(n\) (\(1 \leq n \leq 10^5\)), followed by \(n\) space-separated integers representing the sequence \(a\). The absolute value of each element does not exceed \(10^9\).

outputFormat

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

sample

5
1 -2 3 4 -1

7