Стиснення даних
Нурбакит почав втомлюватися від роботи розробника і вирішив, що йому потрібно хобі. Комп'ютерні ігри виявилися занадто брутальними, а вишивка — надто дорогою. Він спробував займатися музикою, але все звучало як «Даруде - Піщана буря».
Після кількох тижнів пошуків він нарешті знайшов те, що йому підходить. Нурбакит почав брати участь у турнірах з алгоритмічної торгівлі. Він використовує машинне навчання для створення прогнозних моделей.
Зазвичай його набір даних виглядає як масив з n чисел. Масив занадто великий для запуску будь-якого алгоритму глибокого навчання. Нурбакит вирішив, що йому потрібно стиснути масив чисел. Переглядаючи форуми, він натрапив на алгоритм стиснення, відомий як "безглузде стиснення". Цей алгоритм розбиває масив на кілька сегментів і замінює кожен сегмент парою з двох найбільших чисел у ньому. Користувач на ім'я ElonMusk228 припустив, що статистична похибка стиснення залежить від суми цих двох чисел для кожного сегмента. Нурбакит хоче протестувати алгоритм "безглуздого стиснення", тому йому потрібна програма, яка розбиває масив, мінімізуючи суму добутків двох найбільших чисел у кожному сегменті.
Зверніть увагу, що для стиснення масиву кожен сегмент повинен містити щонайменше два числа.
Вхідні дані
Перша строка містить одне ціле число n (2 ≤ n ≤ 10^6).
Друга строка містить n чисел a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10^6) - масив Нурбакита.
Вихідні дані
Виведіть одне ціле число - мінімальну суму добутків пар після стиснення.