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.