Cho một dãy gồm ~n~ số nguyên. Hãy chọn một đoạn liên tiếp, không rỗng của dãy sao cho tổng các phần tử trong đoạn là lớn nhất và in ra tổng đó.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 3000~).

Dòng thứ hai chứa ~n~ số nguyên ~a_1, \dots, a_n~ (~|a_i| \le 10^6~).

Kết quả

In ra tổng lớn nhất của một đoạn liên tiếp.

Ví dụ

Ví dụ 1

Input:

5
1 -2 3 4 -1

Output:

7

Ví dụ 2

Input:

3
-5 -2 -9

Output:

-2

Giải thích

Với 1 -2 3 4 -1 đoạn tốt nhất là 3 4 có tổng ~7~. Hãy thử mọi đoạn ~[l, r]~ và cộng dồn tổng khi ~r~ tăng dần (không cần tính lại từ đầu). Nếu mọi số đều âm thì đáp án là số âm lớn nhất.