Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

SẮN đã mua ~N~ món ngon tuyệt vời cho những con bò, bán cho chúng để nhận lại tiền. SẮN bán một món ăn mỗi ngày và muốn tối đa hóa số tiền anh ta nhận được. Các món ăn rất thú vị vì nhiều lý do:

• Các món ăn được đánh số ~1..N~ và được lưu tuần tự trong một hộp dài mở ở hai đầu. Vào bất cứ ngày nào, SẮN chỉ có thể lấy một món ăn từ một trong hai đầu của hộp.
• Giống như rượu vang hảo hạng và pho mát ngon, các món ăn được cải thiện theo tuổi tác và ra giá cao hơn.
• Các món ăn có chất lượng không đồng nhất: một số tốt hơn và có giá trị cao hơn. Món thứ ~i~ có giá trị ~v[i]~.
• Bò trả nhiều tiền hơn cho các món ăn đã có tuổi lâu hơn: một con bò sẽ trả ~v[i] \cdot a~ cho một món ăn có tuổi ~a~.

Với các giá trị ~v[i]~ của mỗi món ăn đã được xếp tuần tự trong hộp mở hai đầu, hỏi giá trị lớn nhất mà SẮN có thể nhận được là gì nếu anh ta bán các món ăn một cách tối ưu? Món đầu tiên được bán vào ngày 1 và có tuổi ~a = 1~. Mỗi ngày tiếp theo tăng tuổi lên 1.

Dữ liệu vào

• Dòng 1: Một số nguyên duy nhất là ~N~.
• Dòng ~2..N + 1~: Dòng ~i + 1~ chứa giá trị của món ăn thứ ~i~ là ~v[i]~.

Kết quả

• Doanh thu tối đa SẮN có thể đạt được bằng cách bán các món ăn.

Giới hạn

• ~1 \le N \le 2000~, ~1 \le v[i] \le 1000~.

Sample Input 1

5
1 3 1 5 2

Sample Output 1

43

Nguồn: VinhDinhCoder.