問題文

ソーシャルゲームを運営するためには、日々のユーザ数の増減を観察することが欠かせません。

ゲーム会社を運営しているパンチくんは、最もユーザが増加した期間に、何人ユーザが増加したかを調べようとしています。

日々のユーザの増減数 $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$ 行で出力せよ。出力の末尾には改行をいれること。

入力例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$ 日以上であることに注意して下さい。