AT_donuts_live2014_3 ソーシャルゲーム

[problemUrl]: https://atcoder.jp/contests/donuts-live2014/tasks/donuts_live2014_3 ソーシャルゲームを運営するためには、日々のユーザ数の増減を観察することが欠かせません。 ゲーム会社を運営しているパンチくんは、最もユーザが増加した期間に、何人ユーザが増加したかを調べようとしています。 日々のユーザの増減数 $ 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 $ 日以上）のユーザ増減数を、 $ 1 $ 行で出力せよ。出力の末尾には改行をいれること。

### 部分点 $ 1\ ≦\ N\ ≦\ 3000 $ を満たすテストケースに正解した場合、部分点として $ 40 $ 点が与えられる。 ### Sample Explanation 1 $ 3 $ 日目から $ 6 $ 日目までの、 $ (2,\ 3,\ -1,\ 2) $ の増加数 $ 6 $ が最大です。 ### Sample Explanation 2 全期間が、ユーザの増減数が最大となる期間となります。 ### Sample Explanation 3 出力はマイナスとなることがあります。 出力対象となる期間は $ 1 $ 日以上であることに注意して下さい。