📖 Bài giảng & lời giải: đây là Bài tập 4 trong bài giảng Bài 25: Ngăn xếp, hàng đợi đơn điệu trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ 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 xem gợi ý và lờ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

Một dãy $n$ toà nhà liền nhau, toà thứ $i$ rộng $1$ mét và cao $h_i$ mét. Người ta muốn dán một tấm biển hình chữ nhật lên mặt trước các toà nhà: cạnh dưới của tấm biển chạm đất, tấm biển phủ lên một số toà liên tiếp và không được nhô lên khỏi nóc toà nào mà nó phủ (chiều cao tấm biển không vượt quá chiều cao thấp nhất trong các toà đó). Tìm diện tích lớn nhất của tấm biển.

Dữ liệu vào

• Dòng 1: số nguyên $n$ ($1 \le n \le 5 \cdot 10^5$).
• Dòng 2: $n$ số nguyên $h_1, h_2, \ldots, h_n$ ($1 \le h_i \le 10^9$).

Kết quả

In ra một số nguyên là diện tích lớn nhất (mét vuông). Chú ý đáp án có thể vượt quá phạm vi kiểu int.

Sample Input

7
6 2 5 4 5 1 6

Sample Output

12