Максимальная площадь
Максимальная площадь
Хорошо известно, что строительство отеля вблизи морского побережья очень выгодно. Именно поэтому компания International Ocean Investment купила кусок земли на побережье Черного моря (как показано на рисунке) и хотела бы построить отель - как можно больше. По разным причинам отель должен быть с прямоугольным подвалом. Вот почему компания ищет кого-то, чтобы найти прямоугольник с максимальной площадью, который можно было бы расположить на куске земли. Для этой цели ландшафт был разделен на n столбцов равных квадратов (белые на рисунке). Столбцы обозначаются последовательно числами 1, 2, ..., n, слева направо, а прямоугольник должен состоять из целого числа таких квадратов. Затем для каждого столбца подсчитывалось число целых белых квадратов в столбце.
Напишите программу, которая найдет площадь максимального прямоугольника на местности, состоящую из квадратов.
Входные данные
Первая строка содержит натуральное число n (n ≤ 10^6
). Следующая строка содержит n целых чисел d[1]
, d[2]
, ..., d[n]
, где d[i]
(0 < d[i]
≤ 15000) - количество белых квадратов в столбце i.
Выходные данные
Выведите найденную максимальную площадь.
Пример
11 6 5 2 7 8 6 8 3 5 6 7
24