牛たちが新しい事業を始め、Farmer John はその調子を知りたいと思っています。事業は $N$（$1 \leq N \leq 100{,}000$）日間続いており、各日 $i$ に牛たちは純利益 $P_i$（$-1{,}000 \leq P_i \leq 1{,}000$）を記録しました。

Farmer John は、任意の連続した期間に牛たちが得た総利益の最大値を求めたいと考えています。（連続した期間の長さは 1 日から $N$ 日までです。）連続した利益の最大の合計を計算するプログラムを書き、彼を助けてください。

入力

入力は標準入力から読み込んでください。

• 1 行目：1 つの整数 $N$。
• $2..N+1$ 行目：$i+1$ 行目には 1 つの整数 $P_i$ が与えられます。

出力

出力は標準出力に書き出してください。

• 1 行目：任意の連続した期間の利益の合計の最大値を表す 1 つの整数。

入出力例

入力 1

7
-3
4
9
-2
-5
8
-3

出力 1

14

注記

2 番目から 6 番目までの数（4、9、-2、-5、8）の合計を取ると、最大の合計 14 が得られます。

問題作成：Neal Wu、2007