问题文

为了经营社交游戏，必须密切观察每日的用户增减情况。

Punch先生经营一家游戏公司，他想要找出用户增长最多的时间段有多少人增加了用户数。

给定每日的用户增减数 $a_1, a_2, …, a_N$，请找出用户增减数最大的时间段的用户增减数。

输入

输入通过标准输入给出，格式如下所示：

$N$ $a_1$ $a_2$ ... $a_N$

• 第1行给出待调查的时间段的天数 $N (1 ≦ N ≦ 100000)$。
• 第2行给出待调查的时间段内第 $i$ 天的用户增减数 $a_i (-1000 ≦ a_i ≦ 1000)$。

部分分

对于满足 $1 ≦ N ≦ 3000$ 的测试用例，如果正确则可以得到部分分，共40分。

输出

请以一行输出用户增减数最大的时间段（至少1天）的用户增减数。输出末尾换行。

输入示例1

7
3 -4 2 3 -1 2 -1

输出示例1

6

从第3天到第6天，$(2, 3, -1, 2)$ 的增长数为6，是最大的。

输入示例2

3
10 20 30

输出示例2

60

整个时间段都是用户增减数最大的时间段。

输入示例3

3
-4 -2 -5

输出示例3

-2

输出结果可能为负数，请注意输出的时间段至少为1天。