(max1.*)

Bờm vừa dành chiến thắng trong cuộc thi đặc biệt của Phú ông. Với tính keo kiệt của mình Phú Ông chỉ cho Bờm chọn 1 số phần quà liên tục nhau được đặt sẵn trên bàn. Thật may với bảo bối của Đô-rê-mon Bờm nhanh chóng nhận ra giá trị các phần quà.

Giá trị \(n\) phần quà của Phú ông có thể xem là một dãy các số nguyên \(a_{1},\ a_{2},\ldots,a_{n}\ \)trong đó \(a_{i}\) là giá trị của phần quà thứ \(i\). Nếu \(a_{i}\) âm thì phần quà đó không có ý nghĩa với Bờm mà ngược lại Bờm lại thấy thật khó chịu vì phải tốn \(\left| a_{i} \right|\) tiền thuê xe mang nó về nhà rồi cũng chẳng biết làm gì với nó.

Hãy giúp Bờm chọn được một dãy liên tục các phần quà sao cho tổng giá trị là lớn nhất.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\) \((n \leq 10^{6})\)

+ Dòng thứ 2 chứa \(n\) số nguyên \(a_{i}\) tương ứng với giá trị của phần quà thứ \(i\ (|a_{i}| \leq 10^{9})\)

Dữ liệu ra:

+ Ghi một số nguyên duy nhất là giá trị của bài toán

Ví dụ:

Giải thích: Bờm có thể chọn tất cả các phần quà của Phú ông.