1742: 取牌游戏

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：23 Solved：10

Description

       小明在玩取牌游戏，给定一排 n 张卡牌数字，第一个和最后一个数字不可以取出去，其它任意取出去，取出一张卡牌数字时，它有一个代价，这个代价就是与它相邻的两个数的乘积，最终游戏要求除了首尾两位数字外，把其他的卡牌数字都取出来后，它们的代价之和为最小值。 

       如现有一排 5张卡牌数字为: 4 2 5 3 7。 则玩家可能会先取 2，然后取 3 和 5的牌，得分为: 

              4 * 2 * 5 + 5 * 3 * 7 + 4 * 5 * 7 = 40 + 105 + 140 = 285 。

       如果他以另外的顺序取牌，先取 5，然后是 3，最后取 2 的牌，则可取的代价之和更小的得分: 

              2 * 5 * 3 + 2 * 3 * 7 + 4 * 2 * 7 = 30 + 42 + 56 = 128 。

Input

输入第一行一个整数 n。第二行为 n 张卡牌数字 ( 1~100 之间)，数字之间空一格。 

Output

输出一个正整数，表示代价之和的最小数。

Sample Input Copy 

5
4 2 5 3 7

Sample Output Copy 

128

HINT

3 <= n <= 100;  1=<卡牌数字<100