Maximum Subarray Sum

Given an array of integers, your task is to find the maximum sum of any non-empty contiguous subarray. This is a classic problem, often solved with Kadane's algorithm. The problem can be formalized as follows:

Let \( a_1, a_2, \dots, a_n \) be the given integers. We want to compute the maximum value of:

\[ S(i,j) = \sum_{k=i}^{j} a_k, \quad 1 \le i \le j \le n \]

One can use the recurrence relation:

\[ M_i = \max(a_i, M_{i-1}+a_i), \quad \text{with } M_1 = a_1 \]

Your program should read the input from standard input and print the result to standard output.

inputFormat

The first line contains an integer \( N \) denoting the number of elements in the array. The second line contains \( N \) integers separated by spaces.

outputFormat

Output the maximum sum of any non-empty contiguous subarray.

## sample

5
1 -2 3 4 -1

7