Nam đưa cho Việt một dãy số nguyên gồm \(N\) phần tử. Nam thách đố Việt tìm ra một đoạn con liên tiếp (ít nhất một phần tử) sao cho tổng các phần tử trong đoạn đó đạt giá trị lớn nhất. Việt suy nghĩ và viết thuật toán duyệt qua mọi đoạn con liên tiếp \((i, j)\) với \(1 \le i \le j \le N\), độ phức tạp \(O(N^2)\). Khi \(N\) lên tới \(10^5\), thuật toán của Việt chạy quá thời gian (TLE). Bạn hãy giúp Việt cải tiến thuật toán về độ phức tạp \(O(N)\) bằng quy hoạch động nhé!

Dữ liệu vào

• Dòng đầu chứa số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)).

Dữ liệu ra

• In ra một số nguyên duy nhất là tổng lớn nhất của đoạn con liên tiếp tìm được.

Ví dụ

Đầu vào:

5
-2 1 -3 4 -1

Đầu ra:

4

Giải thích: Đoạn con liên tiếp có tổng lớn nhất là [4] có tổng là 4.