Biển quảng cáo lớn nhất trên hàng cột

Bối cảnh và bài toán

Một hàng gồm n cột liền nhau, mỗi cột rộng 1 và có chiều cao h[i]. Cần đặt một biển chữ nhật có đáy nằm trên một đoạn cột liên tiếp; chiều cao biển không vượt quá cột thấp nhất trong đoạn.

Yêu cầu

Tính diện tích lớn nhất của biển có thể đặt.

Input

• Dòng 1: n.
• Dòng 2: n chiều cao h[i].

Output

In diện tích lớn nhất.

Ràng buộc

• 1 <= n <= 2 * 10^5
• 1 <= h[i] <= 10^9

Chấm điểm

Ví dụ 1

Input

8
4 1 5 3 3 2 4 1

Output

10

Giải thích. Đoạn có thể đạt diện tích 10, ví dụ chiều cao 2 trên 5 cột liên tiếp.

Ví dụ 2

Input

4
1000 1000 1000 1000

Output

4000

Giải thích. Dùng toàn bộ 4 cột với chiều cao 1000.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set – Advertisement.

Tham khảo: https://cses.fi/problemset/task/1142/