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 điểm phạt) nếu như lần kiểm tra đó Dũng gian lận. 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ảu “giai đoạn tiến bộ nhất” mà Dũng thực hiện được.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương \(n\ (1 \leq n \leq 10^{6})\)

• Dòng thứ 2 chứa \(n\) số nguyên lần lượt là \(a_{1},a_{2},\ldots,a_{n}\ (\left| a_{i} \right| \leq 10^{9}\ \forall i = 1,2,\ldots,n)\).

Kết quả:

• In một số nguyên duy nhất là kết quả bài toán.

Ràng buộc:

• Có 50% số tests ứng với 50% số điểm của bài có \(n \leq 500\)

• Có 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.

Ví dụ: