Nhân dịp lễ phát động ngày "Môi trường xanh", siêu thị BigC quyết định sẽ trao giải cho chú mèo nào đạt giải trong cuộc thi "Chú mèo bắt chuột giỏi", phần thưởng là chú mèo đạt giải sẽ được quyền lấy các gói kẹo trong siêu thị mà không cần trả tiền. Biết rằng có \(N\) gói kẹo đặt trên giá theo thứ tự từ \(1\) đến \(N\), gói thứ \(i\) có \(a_i\) cái kẹo.

Tom đã giành chiến thắng trong cuộc thi nên được phép chọn các gói kẹo theo thứ tự tăng dần của chỉ số các gọi kẹo sao cho gói kẹo lấy sau không ít kẹo hơn gói kẹo lấy trước. Tom là chú mèo thông minh nên luôn biết cách chọn sao cho lấy được tổng kẹo lớn nhất. Bạn hãy xác định số kẹo mà Tom nhận được là bao nhiêu.

Dữ liệu vào

• Dòng đầu ghi số \(N\) \((1 \lt N \lt 5000)\)
• Dòng thứ hai ghi \(N\) số \(A_i\) là giá trị phần tử thứ \(i\) của dãy \((|A_i| \le 10^9)\)

Dữ liệu ra

• Ghi ra một số nguyên duy nhất là số kẹo Tom nhận được.

Input 1

4
1 2 2 1

Output 1

5

Input 2

6
3 1 5 2 1 3

Output 2

8