輸入一個整數陣列 \( A[1:n]\) ， 請計算 \( A \) 的連續子陣列的最大可能總和，空陣列的和以 \( 0 \) 計算。

輸入格式

第一行是正整數 \( n\) ， 第二行有 \( n \) 整數 \( A[1]\) , \( A[2]\) , \( …\) , \( A[n]\) 。 \(n \) 不超過 \( 1e5\) ，陣列內容絕對值不超過 \( 1e9\) 。

輸出格式

最大可能總和。

範例輸入一

8
4 12 -17 5 8 -2 7 -3

範例輸出一

18

範例輸入二

3
-1 -1 -1

範例輸出二

0