Maximum Subarray Sum

Given an array of integers (A = [a_1, a_2, \dots, a_n]), your task is to find the maximum sum of a contiguous subarray. In other words, compute (\max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k). This problem can be efficiently solved using Kadane's algorithm. The input is provided in the form of a number followed by the list of integers, and you should output a single integer representing the maximum subarray sum.

inputFormat

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

outputFormat

Output a single integer representing the maximum sum of a contiguous subarray.## sample

1
5

5