Максимальная площадь
Хорошо известно, что строительство отеля вблизи морского побережья очень выгодно. Именно поэтому компания 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.
Выходные данные
Выведите найденную максимальную площадь.