Cho một dãy các số nguyên A có N phần tử, hãy tìm đoạn con có tổng lớn nhất của dãy A này.

Mô tả đầu vào

• Dòng đầu chứa số N.
• Dòng thứ 2 chứa N số, là miêu tả dãy A.

Ràng buộc

• |A[i]| ≤ \(10^9\)
• N ≤ \(10^5\)

Mô tả đầu ra

Tổng của đoạn con có tổng lớn nhất tìm được.

6
1 2 3 -1 -1 -1

6