Sau ~n~ bài kiểm tra, điểm của Dũng được ghi lại thành dãy số nguyên ~a_1, a_2, ..., a_n~. Điểm này có thể âm (tương ứng với điểm phạt) nếu như lần kiểm tra đó Dũng gian lận hoặc sử dụng chat GPT. Thầy giáo muốn biết "giai đoạn tiến bộ nhất" mà Dũng thực hiện được, giai đoạn này là dãy các bài kiểm tra liên tiếp của Dũng có tổng điểm lớn nhất.

Yêu cầu: Hãy xác định tổng điểm của "giai đoạn tiến bộ nhất" mà Dũng thực hiện được.

Input

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

Output

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

Sample Input 1

9
-90 1 3 -2 5 -1 2 5 -3

Sample Output 1

13

Giải thích: Dãy điểm cần tìm là 1, 3, -2, 5, -1, 2, 5 có tổng 1+3-2+5-1+2+5=13

Subtasks

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