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

Гистограмма

Гистограмма

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

Гистограмма является многоугольником, сформированным из последовательности прямоугольников, выровненных на общей базовой линии. Прямоугольники имеют равную ширину, но могут иметь различные высоты. Например, фигура слева показывает гистограмму, которая состоит из прямоугольников с высотами 2, 1, 4, 5, 1, 3, 3. Все прямоугольники на этом рисунке имеют ширину, равную 1.

Обычно гистограммы используются для представления дискретных распределений, например, частоты символов в текстах. Отметьте, что порядок прямоугольников очень важен. Вычислите область самого большого прямоугольника в гистограмме, который также находится на общей базовой линии. На рисунке справа заштрихованная фигура является самым большим выровненным прямоугольником на изображенной гистограмме.

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

В первой строке записано число n~(0 \le n \le 10^6) — количество прямоугольников гистограммы. Затем следует n целых чисел h_1, ..., h_n~(0 \le h_i \le 10^9). Эти числа обозначают высоты прямоугольников гистограммы слева направо. Ширина каждого прямоугольника равна 1.

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

Вывести площадь самого большого прямоугольника в гистограмме. Помните, что этот прямоугольник должен быть на общей базовой линии.

Пример

Входные данные #1
7 2 1 4 5 1 3 3
Выходные данные #1
8
Входные данные #4
8 2 1 2 0 3 2 2 3
Выходные данные #4
8
Источник Отборочный тур Всероссийской командной олимпиады школьников 2009/2010 учебный год