Sau n bài kiểm tra, điểm của Dũng được ghi lại thành dãy số nguyên a1, a2, ..., an. Đ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.

Dữ liệu:

Nhập từ bàn phím

- Dòng đầu tiên chứa số nguyên dương n (1 <= n <= 10^6)

- Dòng thứ hai chứa n số nguyên lần lượt là a1, a2, ..., an (|ai| <= 10^9 với mọi i = 1, 2, ..., n). Hai số liên tiếp cách nhau bằng khoảng trắng (space).

Kết quả:

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

Ràng buộc:

- Có 50% số tests ứng với 50% số điểm của bài có n <= 500

- 30% số tests tiếp theo ứng với 30% số điểm của bài có n <= 5000

- Các tests còn lại không có ràng buộc bổ sung

Ví dụ:

Dữ liệu:
9
-90 1 3 -2 5 -1 2 5 -3

Kết quả:
13

Giải thích: Dãy điểm cần tìm là 1, 3, -2, 5, -1, 2, 5 có tổng 1+3-2+5-1+2+5=13