Given an integer array ~a~ of length ~N~, find the maximum subarray sum.

A subarray is defined as a contiguous range in an array, and a subarray sum is defined as the sum of all elements in the contiguous range.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10^5)~.

The second line will contain ~N~ integers, ~a_1, a_2, \ldots, a_N~ ~(-10^9 \le a_i \le 10^9)~.

Output Specification

Output the maximum subarray sum in the array. Note that the subarray may be the entire array. However, the subarray must contain at least one element.

Subtasks

Subtask 1 [10%]

~N \le 100~

Subtask 2 [30%]

~N \le 1~ ~000~

Subtask 2 [60%]

No further constraints.

Sample Input 1

5
1 -3 4 2 2

Sample Output 1

8

Sample Input 2

7
5 2 -4 7 9 -2 1

Sample Output 2

19

Explanation For Sample 2

We can take the subarray ~a[0,4]~ (~0~-indexed) for a total sum of ~5+2+(-4)+7+9 = 19~.