Maximum Subarray Sum

Given an array of n integers, your task is to find the maximum sum of any contiguous subarray. This is a classic problem which can be efficiently solved using Kadane's algorithm.

You are required to compute the value represented by the following formula in LaTeX format:

\(\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k\)

For example, if the input is [1, -3, 2, 1, -1], the maximum subarray sum is 3, which comes from the subarray [2, 1].

inputFormat

The input is provided via stdin and consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 10⁵) representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output via stdout a single integer representing the maximum sum of any contiguous subarray.

## sample

1
-1

-1

</p>