Đoạn con lớn nhất

Cho mảng số nguyên gồm \(n\) phần tử \(a_1, a_2, \ldots, a_n\). Hãy tìm giá trị lớn nhất của tổng đoạn con liên tiếp \(\sum_{i=l}^r a_i\) với \(1\le l\le r\le n\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 2\cdot 10^5\)).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, \ldots, a_n\) (\(|a_i|\le 10^9\)).

Output

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

Scoring

• Subtask 1 (50 điểm): \(n\le 2\cdot 10^3\).
• Subtask 2 (50 điểm): không ràng buộc thêm.

Sample Input 1

5
-1 2 3 -5 4

Sample Output 1

5