Maximum Subarray Sum

You are given an array of n integers. Your task is to determine the maximum possible sum of any contiguous subarray of the given array.

The solution can be derived using Kadane's algorithm. In mathematical terms, let the input array be \(a_1, a_2, \dots, a_n\). We need to compute:

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

It is guaranteed that n is at least 1. The array may contain negative numbers.

inputFormat

The first line contains an integer n representing the number of elements in the array.

The second line contains n space-separated integers representing the elements of the array.

outputFormat

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

## sample

5
1 2 3 -2 5

9