Maximum Subarray Sum

You are given an array of integers and your task is to find the maximum sum of any non-empty subarray. A subarray is a contiguous part of the array. This problem is a classic application of Kadane's algorithm and can be stated mathematically as:

Given an array \(a_1, a_2, \dots, a_n\), find the maximum value of \(\sum_{i=l}^{r} a_i\) for any \(1 \leq l \leq r \leq n\).

You need to read the array from standard input and output the result to standard output.

inputFormat

The first line contains an integer \(n\) which is the number of elements in the array. The second line contains \(n\) space-separated integers representing the elements of the array.

Example:

5
1 2 3 4 5

outputFormat

Output a single integer which is the maximum sum of a contiguous subarray.

Example:

15

## sample

1
1

1