Các con bò đã mở một hoạt động kinh doanh mới, và Farmer John muốn xem chúng làm ăn ra sao. Hoạt động đã diễn ra trong $N$ ($1 \leq N \leq 100{,}000$) ngày, và mỗi ngày $i$ các con bò ghi lại lợi nhuận ròng $P_i$ ($-1{,}000 \leq P_i \leq 1{,}000$).

Farmer John muốn tìm tổng lợi nhuận lớn nhất mà các con bò kiếm được trong bất kỳ khoảng thời gian liên tiếp nào. (Lưu ý rằng độ dài một khoảng thời gian liên tiếp có thể từ một ngày đến $N$ ngày.) Hãy giúp ông bằng cách viết chương trình tính tổng lớn nhất của các lợi nhuận liên tiếp.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn.

• Dòng 1: một số nguyên duy nhất $N$.
• Các dòng $2..N+1$: dòng $i+1$ chứa một số nguyên duy nhất $P_i$.

Dữ liệu ra

Ghi kết quả ra đầu ra chuẩn.

• Dòng 1: một số nguyên duy nhất biểu thị tổng lợi nhuận lớn nhất trong bất kỳ khoảng thời gian liên tiếp nào.

Ví dụ

Dữ liệu vào 1

7
-3
4
9
-2
-5
8
-3

Dữ liệu ra 1

14

Ghi chú

Tổng lớn nhất đạt được khi lấy tổng từ số thứ hai đến số thứ sáu (4, 9, -2, -5, 8), cho kết quả 14.

Tác giả bài toán: Neal Wu, 2007