Головоломка умножения

В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от неё. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остаётся только две карты.

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

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

Если бы он взял карты в обратном порядке, то есть $50$, затем $20$, затем $1$, количество очков было бы таким:

Входные данные

В первой строке находится количество карт $n$, во второй — $n(3\le n\le 100)$ чисел на картах. Все числа на картах целые от $1$ до $100$.

Выходные данные

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

Примеры