Cho số nguyên dương n và dãy số nguyên a1, a2, …, an. Tìm giá trị lớn nhất của biểu thức (a[i]+a[i+1]+… +a[j]) với 1≤i≤j≤n).

Input:

• Dòng 1: chứa số n.

• Dòng 2: chứa n số a1, a2, …, an (|ai|<=10^9)

Output

• Ghi ra giá trị lớn nhất của biểu thức.

Sample Input:

7 
8 -10 6 -5 9 1 -3

Sample Output:

11

Giới hạn:

Sub1: n≤200 ;   
Sub2: n≤5000;   
Sub3: n≤10^6