A tide gauge records n consecutive net-change readings, one per interval; each reading is the signed change in water level during that interval (it may be negative). A contiguous run of intervals accumulates the sum of its readings. Find the largest total accumulated by any non-empty contiguous run.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the readings in time order.
Output format
A single integer: the maximum sum achievable by a non-empty contiguous run.
Constraints
- 1 <= n <= 100000
- -1000000 <= each reading <= 1000000