乳牛們開辦了一項新業務，Farmer John 想看看她們經營得如何。這項業務已經運作了 $N$（$1 \leq N \leq 100{,}000$）天，每天 $i$ 乳牛們都記錄淨利潤 $P_i$（$-1{,}000 \leq P_i \leq 1{,}000$）。
Farmer John 想求乳牛們在任意一段連續時間內獲得的最大總利潤。（注意，一段連續時間的長度可以是一天到 $N$ 天。）請編寫程式計算連續利潤的最大和來幫助他。
輸入格式
從標準輸入讀取輸入。
- 第 1 行：一個整數 $N$。
- 第 $2..N+1$ 行：第 $i+1$ 行包含一個整數 $P_i$。
輸出格式
將輸出寫入標準輸出。
- 第 1 行：一個整數，表示任意一段連續時間內的利潤總和的最大值。
範例
輸入格式 1
7 -3 4 9 -2 -5 8 -3
輸出格式 1
14
說明
取第 2 個數到第 6 個數（4、9、-2、-5、8）的和，可以得到最大和 14。
題目作者：Neal Wu，2007