Đề bài

Cho dãy số $A$ gồm $N$ số nguyên (có thể chứa số âm). Hãy tìm một đoạn con liên tiếp trong dãy sao cho tổng các phần tử của đoạn con đó là lớn nhất. In ra giá trị tổng lớn nhất đó.

Dữ liệu vào

Dòng 1: Số nguyên dương $N$ ($1 \le N \le 10^5$).

Dòng 2: $N$ số nguyên $A_1, ..., A_N$.

Dữ liệu ra

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

Ví dụ