Given an array of n integers, Steve now wonders what can be the maximum sum of a sub-array. Help him find the answer.

Input

The first line of input contains an integer n: The number of elements in array

The second line contains array of n integers.

Output

Print one integer: Maximum sum of any of the subarray,

Constraints

$(1 \le n \le 10^5)$

$(-10^9 \le A_i \le 10^9)$