Given an array of integers, we want you to find the sub-array with the maximum sum.

A subarray of an array X is an array that can be formed by taking zero or more contiguous elements of X.

Input Specification

The input file starts with a line containing one integer \(N\) the length of the array (\(1\leq N \leq 10^6\)).

The second line contains \(N\) space-separated integers \(A_i\) denoting the elements of the array (\( -10^5 \leq A_i \leq 10^5\)).

Output Specification

Output one integer : the maximum sub of all sub-arrays.

Sample Input

10
10 -10 -6 -2 6 5 -3 8 9 -10

Sample Output

25