eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Максимальная площадь

Максимальная площадь

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Хорошо известно, что строительство отеля вблизи морского побережья очень выгодно. Именно поэтому компания International Ocean Investment купила кусок земли на побережье Черного моря (как показано на рисунке) и хотела бы построить отель - как можно больше. По разным причинам отель должен быть с прямоугольным подвалом. Вот почему компания ищет кого-то, чтобы найти прямоугольник с максимальной площадью, который можно было бы расположить на куске земли. Для этой цели ландшафт был разделен на n столбцов равных квадратов (белые на рисунке). Столбцы обозначаются последовательно числами 1, 2, ..., n, слева направо, а прямоугольник должен состоять из целого числа таких квадратов. Затем для каждого столбца подсчитывалось число целых белых квадратов в столбце.

prb8590.gif

Напишите программу, которая найдет площадь максимального прямоугольника на местности, состоящую из квадратов.

Входные данные

Первая строка содержит натуральное число n (n10^6). Следующая строка содержит n целых чисел d[1], d[2], ..., d[n], где d[i] (0 < d[i]15000) - количество белых квадратов в столбце i.

Выходные данные

Выведите найденную максимальную площадь.

Пример

Входные данные #1
11
6 5 2 7 8 6 8 3 5 6 7
Выходные данные #1
24
Источник 2015 VII International autumn tournament in informatics, Shumen, Junior, Задача B