Hàng rào của nhà Mr Bean gồm một dãy n tấm gỗ có chiều rộng bằng 1 đơn vị và chiều cao lần lượt là a1, a2, …, an.
Mặt tiền nhà của Mr Bean là nơi rất nhiều người qua lại do đó Mr Bean quyết định cho thuê quảng cáo. Tất nhiên các tấm quảng cáo có dạng hình chữ nhật, chiều rộng phủ lên một số nguyên lần các tấm gỗ của hàng rào và không có phần nào của tấm quảng cáo mà phía sau không có tấm gỗ chắn.
Hãy tính diện tích lớn nhất của một tấm quảng cáo như vậy
INPUT
OUTPUT
INPUT |
OUTPUT |
4 3 4 3 1 |
9 |
4 1 2 1 3 |
4 |
*Giải thích ví dụ 1:
Hàng rào ban đầu:
- Có thể tạo ra một trong những tấm biển quảng cáo như sau:
Tấm 1: |
Tấm này có chiều ngang bằng 4, chiều cao bằng 1.
|
Tấm 2: |
Tấm này có chiều ngang bằng 3, chiều cao bằng 3.
|
Tấm 3 |
Tấm này có chiều ngang bằng 1, chiều cao bằng 4.
|
Vậy tấm có diện tích lớn nhất là 9