Maximum Subarray Sum

You are given an integer n representing the number of elements in an array, followed by n integers. Your task is to compute the maximum sum of any contiguous subarray.

The problem can be formulated mathematically as finding $$ \max_{1 \le i \le j \le n} \sum_{k=i}^{j} A[k], $$ where \( A[k] \) are the elements of the array.

If the array is empty (n = 0), output 0.

inputFormat

The first line contains a single integer n (n ≥ 0) representing the number of elements in the array. If n > 0, the second line contains n space-separated integers representing the array elements.

outputFormat

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

## sample

5
1 2 -3 4 5

9

</p>