Ломиголовка множення#877
У ломиголовку множення грають з рядом карток, кожна з яких містить одне додатнє ціле число. Під час ходу гравець забирає одну з карток з ряду і отримує число очок, рівне добутку числа на прибраній картці та чисел на картках, які лежать безпосередньо ліворуч і праворуч від неї. Не дозволяється прибирати першу і останню картки ряду. Після останнього ходу у ряду залишається лише дві картки.
Мета гри — прибрати картки у такому порядку, щоб мінімізувати загальну кількість набраних очок.
Наприклад, якщо картки містять числа , , , та , гравець може взяти картку з числом , потім і , отримуючи очки
Якби він взяв картки у зворотному порядку, тобто , потім , потім , кількість очок була б такою:
У першому рядку знаходиться число карток (3 \leq n \leq 100), у другому — чисел на картках. Числа на картках цілі від до .
Виведіть одне ціле число — мінімально можливу кількість очок.
Приклад 1