Cho dãy số nguyên \(a_1, a_2,..., a_N(|a_i| < 10^9, N ≤ 10^5)\). Một tập hợp khác rỗng các số hạng liên tiếp \({a_i, a_{i+1},..., a_k} (i \le k)\) gọi là một đoạn con của dãy đó. Với mỗi đoạn con ta tính tổng tất cả các số hạng của nó.

Yêu cầu: Tìm giá trị lớn nhất trong số các tổng của các đoạn con của dãy đã cho.

Dữ liệu vào:

• Dòng đầu chứa số \(N\);
• Dòng thứ hai là một dãy số nguyên gồm \(N\) phần tử: \(a_1, a_2,..., a_N.\) Các số cách nhau một dấu cách.

Dữ liệu ra: Một số nguyên là giá trị tổng đoạn con lớn nhất tìm được.

Ví dụ:

Input

7
1 -2 -1 4 -1 5 -2

Output

8

Giải thích:

• Đoạn con \((a_4, a_5, a_6)\) có tổng lớn nhất là: \(4 – 1 + 5 = 8\)

Ràng buộc:

• Có 70% số test ứng với 70% số điểm của bài có \(N ≤ 3x10^3\);
• Có 30% số test khác ứng với 30% số điểm còn lại của bài.