Максимальна площа#8590
Відомо, що будівництво готелю біля морського узбережжя є дуже вигідним. Саме тому компанія International Ocean Investment придбала ділянку землі на узбережжі Чорного моря (як показано на рисунку) і хоче побудувати готель - якомога більший. З різних причин готель повинен мати прямокутний фундамент. Тому компанія шукає когось, хто зможе знайти прямокутник з максимальною площею, який можна розмістити на цій ділянці. Для цього ландшафт було поділено на стовпців однакових квадратів (білі на рисунку). Стовпці пронумеровані послідовно числами 1, 2, \ldots, n зліва направо, і прямокутник повинен складатися з цілого числа таких квадратів. Потім для кожного стовпця було підраховано кількість цілих білих квадратів у стовпці.
Напишіть програму, яка визначить площу найбільшого прямокутника на ділянці, що складається з квадратів.
Перший рядок містить натуральне число (n \le 10^6). Наступний рядок містить цілих чисел d_1, d_2, \ldots, d_n, де d_i (0 < d_i \le 15000) - кількість білих квадратів у стовпці .
Виведіть знайдену максимальну площу.
Приклад 1