Bài 23: Bể chứa nước lớn nhất

Yêu cầu: Có ~N~ bức tường thẳng đứng xếp thành hàng, bức tường thứ ~i~ có chiều cao ~H_i~. Khoảng cách giữa 2 bức tường ~i~ và ~j~ là ~|i - j|~. Khi đổ nước vào giữa 2 bức tường, lượng nước chứa được là ~|i - j| \times \min(H_i, H_j)~. Hãy tìm lượng nước lớn nhất có thể chứa được.

Giới hạn:

• ~2 \le N \le 10^5~
• ~1 \le H_i \le 10^4~
• Thời gian: 1.0s

Ví dụ:

Input:

6
1 5 4 3 2 4

Output:

16

(Giải thích: Chọn bức tường ở vị trí 2 (cao 5) và vị trí 6 (cao 4). Thể tích = (6-2) * min(5,4) = 4 * 4 = 16.)