Maximum Subarray

Problem statement

A delivery team logs hourly changes in its balance. Select a nonempty consecutive stretch of hours with the largest total change. A negative answer is possible when every hour loses money.

Input format

First line: n. Second line: n space-separated integers.

Output format

Print the largest sum of a nonempty contiguous segment.

Constraints

1 <= n <= 100000; -10000 <= each value <= 10000. Use 64-bit integers for sums.

Sample input

7
-4 5 -2 6 -8 3 1

Sample output

9