Given an array of \(n\) integers, your task is to find the maximum sum of values in a contiguous, nonempty subarray.

Input

• The first input line has an integer \(n\): the size of the array.
• The second line has \(n\) integers \(x_1,x_2,\ldots,x_n\): the array values.

Output

• Print one integer: the maximum subarray sum.

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(−10^9 \leq x_i \leq 10^9\)

Example

Sample input

8  
-1 3 -2 5 3 -5 2 2

Sample output

9