Given an array of

`n`

integers, find a contiguous subarray with the maximum sum of values. Input

The first line of the input contains an integer

`n`

- number of elements in the array (1 ≤ n ≤ ).The next line contains

`n`

integers separated by a space, that represent the elements of the array . Output

The program should print a single integer - the highest possible sum of the subarrays in the given array.

Examples

Input | Output |

9
-2 1 -3 4 -1 3 1 -4 -2 | 7 |

10
1 -2 3 4 -3 1 7 -10 -20 4 | 12 |

Explanation

- -2 1 -3
`4 -1 3 1`

-4 -2 → The sum of the highlighted subarray is (4 - 1 + 3 + 1) = 7

- 1 -2
`3 4 -3 1 7`

-10 -20 4 → 3 + 4 -3 + 1 + 7 = 12

## Can you make this even better 😎?

It’s possible to solve this problem without any additional arrays. Can you do that?