Ломиголовка множення

У ломиголовку множення грають рядом карток, кожна з яких містить одне додатнє ціле число. Під час ходу гравець забирає одну з карток з ряду і отримує число очоко, рівне добутку числа на прибраній карті та чисел на картках, які лежать безпосередньо ліворуч і праворуч від неї. Не дозволяється прибирати першу і останю картки ряду. Після останнього ходу у ряду залишається лише дві картки.

Мета гри — прибрати картки у такому порядку, щоб мінімізувати загальну кількість набраних очок.

Наприклад, якщо картки містять числа $10,1,50,20$ та $5$, гравець може взяти картку з числом $1$, потім $20$ і $50$, отримуючи очки

Якби він взяв картки у зворотньому порядку, тобто $50$, потім $20$, потім $1$, кількість очок була б такою:

Вхідні дані

У першому рядку знаходиться число карток $n(3\le n\le 100)$, у другому — $n$ чисел на картках. Числа на картках цілі від $1$ до $100$.

Вихідні дані

Вивести одне ціле число — мінімально можливу кількість очок.

Приклади