#$P1651. 乘法谜题$

题目描述

乘法谜题使用一排卡片进行游戏，每张卡片上有一个正整数。在每一步移动中，玩家从这排卡片中取出一张（不能取出首尾两张卡片），得分等于该卡片上的数字与左右两边卡片上数字的乘积。当最后一步移动结束后，这排卡片中只剩下两张卡片。

游戏的目标是通过选择取卡片的顺序，使得总得分最小。

例如，若卡片上的数字为 $10$ $1$ $50$ $20$ $5$，玩家可能先取 $1$，再取 $20$，最后取 $50$，得分为：
$ 10 \times 1 \times 50 + 50 \times 20 \times 5 + 10 \times 50 \times 5 = 500 + 5000 + 2500 = 8000 $
如果按相反的顺序取卡片（先取 $50$，再取 $20$，最后取 $1$），得分为：
$ 1 \times 50 \times 20 + 1 \times 20 \times 5 + 10 \times 1 \times 5 = 1000 + 100 + 50 = 1150 $

输入

第一行包含卡片数量 $N$（$3 \leq N \leq 100$）。
第二行包含 $N$ 个整数（范围 $1$ 到 $100$），用空格分隔。

输出

输出一个整数，表示最小总得分。

输入数据 1

6  
10 1 50 50 20 5  

输出数据 1

3650  

来源

2001年东北欧地区，远东次区域