Pretty#10957

Pretty

0.4 seconds

256 megabytes

Easy

In a given array of numbers, your task is to find a subarray with the largest possible sum. The subarray must contain at least one element.

Input

The first line contains one integer $n$ $(1 \leq n \leq 1 0^{5})$ (1 \leq n \leq 10^5), representing the number of elements in the array.

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n $(- 1 0^{4} \leq a_{i} \leq 1 0^{4})$ (-10^4 \leq a_i \leq 10^4), representing the elements of the array.

Output

Print one integer, representing the largest possible sum of a subarray.

Examples

Example

5
-2 1 -3 4 -1 2 1 -5 4

Example 1

Example 2

Note

In the given example, the subarray with the largest sum is $[4, - 1, 2, 1]$ [4, -1, 2, 1], whose sum equals $6$ .