Cho một dãy số nguyên gồm N phần tử ~a_1,a_2,…,a_N. Gọi f(L,R)=a_L+a_(L+1)+⋯+a_R (1≤L≤R≤N).~

Yêu cầu: Tìm giá trị f(L,R) lớn nhất.

Input: Dòng đầu gồm duy nhất một số nguyên dương N (~N≤〖10〗^6 )~; Dòng tiếp theo gồm N số nguyên ~a_1,a_2,…,a_N (|a_i |≤〖10〗^9 ~). Output: In ra kết quả bài toán.

Ví dụ:
INPUT               OUTPUT
5
6 -4 5 2 -1          9