Get Max Aggregate Temperature Change

The aggregate temperature change of day i is the larger of the prefix sum from day 1 to day i and the suffix sum from day i to the last day; both parts include day i. Return the maximum aggregate temperature change over all days; an empty prefix or suffix is not allowed.

输入格式

The first line contains n; the second line contains n temperature changes. 1≤n≤100000, −10^9≤change≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

3
6 -2 5

输出：

9

样例 2

输入：

3
-1 2 3

输出：

5

样例 3

输入：

3
-5 -2 -8

输出：

-5

样例说明

The answers are 9, 5 and −5; in the last example you cannot choose an empty segment to get 0.