Gia đình nhà Nam là một doanh nghiệp lớn, bản thân Nam vừa tốt nghiệp ngành Quản trị kinh doanh nên Nam được gia đình giao cho quản lí chuỗi cửa hàng tiện lợi Thành Đạt. Áp dụng công nghệ số, Nam dùng phần mềm quản lí kinh doanh cập nhật lợi nhuận theo từng ngày trong \(n\) ngày, trong đó ngày thứ \(i\) đạt lợi nhuận là \(a_i\).

Nhân kỉ niệm ngày thành lập công ty, Nam muốn minh chứng việc kinh doanh ngày càng phát triển bằng cách chọn ra một ngày hoặc một số ngày trong \(n\) ngày trên thỏa mãn lợi nhuận ngày sau lớn hơn lợi nhuận ngày trước và tổng lợi nhuận các ngày được chọn là lớn nhất.

Các bạn hãy giúp Nam giải quyết vấn đề trên.

Dữ liệu:

• Dòng đầu tiên gồm số nguyên dương \(n (1≤ n≤ 10^6);\)

• Dòng thứ hai gồm \(n\) số nguyên không âm \(a_1,a_2,..,a_n (0≤a_i≤10^9, 1 ≤i≤n). \)

Kết quả:

• Ghi một số nguyên duy nhất là tổng lợi nhuận lớn nhất.

Sample Input

6
1 7 2 7 8 5

Sample Output

18

Giải tích:

• Chọn các ngày:1, 3, 4, 5 tương ứng với dãy con: 1, 2, 7, 8

Ràng buộc:

• Có 30% số test tương ứng với 30% số điểm của bài có \(n≤20;\)

• Có 40% số test tương ứng với 40% số điểm của bài có \(20<n ≤ 1000;\)

• Có 30% số test tương ứng với 30% số điểm của bài có \(1000<n≤10^5.\)