Sau \(n\) bài kiểm tra, điểm của Dũng được ghi lại thành dãy số nguyên \(a_1, a_2, \ldots, a_n\). Điểm này có thể âm (tương ứng với điểm phạt) nếu như lần kiểm tra đó Dũng gian lận hoặc sử dụng chat GPT. Thầy giáo muốn biết "giai đoạn tiến bộ nhất" mà Dũng thực hiện được, giai đoạn này là dãy các bài kiểm tra liên tiếp của Dũng có tổng điểm lớn nhất.

Yêu cầu: Hãy xác định tổng điểm của "giai đoạn tiến bộ nhất" mà Dũng thực hiện được.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \leq n \leq 10^6)\)
• Dòng thứ hai chứa \(n\) số nguyên lần lượt là \(a_1, a_2, \ldots, a_n\) \((|a_i| \leq 10^9\) với mọi \(i = 1,2,\ldots,n)\). Hai số liên tiếp cách nhau bằng khoảng trống (space)

Output

• In ra màn hình một số nguyên duy nhất là kết quả tìm được.

Scoring

• Có \(50\%\) số tests ứng với \(50\%\) số điểm của bài có \(n \leq 500\)
• \(30\%\) số tests tiếp theo ứng với \(30\%\) số điểm của bài có \(n \leq 5000\)
• Các tests còn lại không có ràng buộc bổ sung

Example

9
-90 1 3 -2 5 -1 2 5 -3

13