Задачи
Головоломка умножения
Головоломка умножения
В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от неё. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остаётся только две карты.
Цель игры --- убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.
Например, если карты содержат числа $10, 1, 50, 20$ и $5$, игрок может взять карту с числом $1$, затем $20$ и $50$, получая очки
$$
10 \cdot 1 \cdot 50 + 50 \cdot 20 \cdot 5 + 10 \cdot 50 \cdot 5 = 500 + 5000 + 2500 = 8000
$$
Если бы он взял карты в обратном порядке, то есть $50$, затем $20$, затем $1$, количество очков было бы таким:
$$
1 \cdot 50 \cdot 20 + 1 \cdot 20 \cdot 5 + 10 \cdot 1 \cdot 5 = 1000 + 100 + 50 = 1150
$$
\InputFile
В первой строке находится количество карт $n$, во второй --- $n\:(3 \le n \le 100)$ чисел на картах. Все числа на картах целые от $1$ до $100$.
\OutputFile
Вывести одно целое число --- минимально возможное число очков.
Входные данные #1
6 10 1 50 50 20 5
Выходные данные #1
3650