В головоломку умножения играют с рядом карт, каждая из которых содержит одно положительное целое число. Во время хода игрок убирает одну карту из ряда и получает число очков, равное произведению числа на убранной карте и чисел на картах, лежащих непосредственно слева и справа от неё. Не разрешено убирать первую и последнюю карты ряда. После последнего хода в ряду остаётся только две карты.
Цель игры — убрать карты в таком порядке, чтобы минимизировать общее количество набранных очков.
Например, если карты содержат числа 10,1,50,20 и 5, игрок может взять карту с числом 1, затем 20 и 50, получая очки
Если бы он взял карты в обратном порядке, то есть 50, затем 20, затем 1, количество очков было бы таким:
В первой строке находится количество карт n, во второй — n(3≤n≤100) чисел на картах. Все числа на картах целые от 1 до 100.
Вывести одно целое число — минимально возможное число очков.