Cho một mảng N số nguyên, nhiệm vụ của bạn là tìm tổng giá trị lớn nhất trong một mảng con liền kề, không rỗng.

Đầu vào

Dòng đầu tiên có một số nguyênN: kích thước của mảng.

Dòng thứ hai cóNsố nguyên x1,x2,,, x_n: các giá trị mảng.

Đầu ra

In ra một số nguyên: tổng mảng con lớn nhất.

Ví dụ

Đầu vào:

8

-1 3 -2 5 3 -5 2 2

Đầu ra:

9