Cho dãy ~n~ số nguyên ~a_1, a_2, ..., a_n~. Hãy tìm dãy con gồm các số liên tiếp của dãy trên ~a_i, a_{i+1}, ..., a_j~ (~1 \le i \le j \le n~) sao cho tổng ~a_i + a_{i+1} + ... + a_j~ đạt giá trị lớn nhất.

Yêu cầu: Hãy tính giá trị tổng lớn nhất này.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n \le 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^3; \forall i = 1, 2, ..., n~). Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống (space).

Output

Ghi ra màn hình duy nhất một số nguyên là kết quả tìm được.

Sample Input 1

5
-5 2 -1 0 4

Sample Output 1

5

Giải thích: Dãy con có tổng lớn nhất là 2, -1, 0, 4 (tổng là 5).

Subtasks

• Có 40% số tests ứng với 40% số điểm của bài có ~n \le 500~.
• 40% số tests tiếp theo ứng với 40% số điểm của bài có ~n \le 5000~.
• 20% số tests còn lại không có ràng buộc bổ sung.