Герой відомого мультсеріала Коливан вирішив побудувати собі басейн. Оскільки він дуже скупий, він намагається використати будівлю, що вже існує.
Будівля являє собою абсолютно рівний коридор одиничної ширини, в якому є N перегородок. Якщо розмістити вісь Х вздовж коридору, усі перегородки будуть знаходитись точно в її цілочисельних координатах з кроком 1, причому по ширині перегородки займають весь коридор, а висоти можуть відрізнятися. Басейн, що створюється, повинен мати максимально великий можливий об’єм за умови, що з усіх існуючих перегородок потрібно залишити тільки дві та збільшувати їх висоту заборонено.
Формат введення/виведення.
Програма flooding зчитує з клавіатури (стандартного пристрою введення) ціле число N (2<=N<=105) – кількість перегородок. Потім зчитується N цілих чисел аi (1<=аi<=109) – висоти перегородок.
Програма flooding виводить на екран (стандартний пристрій виведення) єдине число – максимально можливий об’єм створюваного басейна з урахуванням вказаних обмежень .
Приклад вхідних та вихідних даних.
|
Введення |
Виведення |
|
4 1 2 1 3 |
4 |