Cho dãy ~A~ có ~N~ phần tử. Một đoạn con của dãy ~A~ là dãy các phần tử liên tiếp ~A_i, A_{i+1}, … A_j~ mà ~i \le j~. Tổng của đoạn con là ~A_i + A_{i+1} + … + A_j~.

Yêu cầu:

• Hãy tìm đoạn con có tổng lớn nhất.

Giới hạn:

• ~N \le 10^5~ và |~A_i~| ~\le 10^9~

Dữ liệu vào:

• Dòng đầu tiên nhập vào số nguyên dương N.
• Dòng thứ hai, nhập vào N số nguyên, số thứ i là Ai

Kết quả:

• In ra một số nguyên duy nhất là tổng lớn nhất tìm được.

Ví dụ: