程設的教學每次上課令你的收穫程度都不一樣

現在總共有n堂社課 你不想斷斷續續地來

但你想要最大化你的收穫程度

因此你選擇開始課程的堂數i 跟結束課程的堂數j

而在第i堂課到第j堂課你每堂都要到(就算收穫是負的)

請問 在讓你自由選擇i j的情況下 你最大可以收穫到多少呢？

Input

第一行為一正整數n 代表總共有n堂社課 再來一行有以空白分隔的n個整數，依序表示第1堂到第n堂社課你的收穫程度

Output

輸出你的最大收穫

Constraints

1<=n<=2000000 -100000000<=a[i]<=100000000

(5%) n<=2

(10%) n<=20

(10%) 對於所有1<=i<=n,a[i]>=0

(15%) 對於所有2<=i<=n,a[i]<=a[i-1]

(20%) n<=200

(30%) n<=20000

(10%) n<=2000000

Sample Input

5

2 -1 5 -4 3

Sample Output

6