Гістограма

Гістограма є многокутником, сформованим з послідовності прямокутників, вирівняних на спільній базовій лінії. Прямокутники мають однакову ширину, але можуть мати різні висоти. Наприклад, фігура ліворуч показує гістограму, яка складається з прямокутників з висотами $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$.

Вихідні дані

Вивести площу найбільшого прямокутника в гістограмі. Пам'ятайте, що цей прямокутник повинен бути на спільній базовій лінії.

Приклади