An tham gia một trò chơi mô phỏng đầu tư chứng khoán do lớp tổ chức nhân ngày hội Toán. Mỗi ngày trong \(N\) ngày liên tiếp, An đều đầu tư và thu về kết quả \(a_i\): nếu \(a_i\) dương thì ngày đó lãi, còn nếu \(a_i\) âm thì ngày đó lỗ. An được chọn một khoảng thời gian gồm các ngày liên tiếp để ghi nhận kết quả; nếu cảm thấy toàn bộ các ngày đều cho kết quả không tốt thì An có thể chọn không đầu tư ngày nào, khi đó tổng lãi coi như \(0\).

An muốn chọn khoảng thời gian (hoặc không chọn gì cả) sao cho tổng lãi thu được là lớn nhất có thể. Hãy giúp An.

Định dạng đầu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(-10^9 \le a_i \le 10^9\)).

Định dạng đầu ra

• In ra tổng lãi lớn nhất An đạt được.

Ví dụ

Input:

9
-2 1 -3 4 -1 2 1 -5 4

Output:

6

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 20\).
• \(30\%\) số điểm ứng với \(N \le 2000\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.