题目描述

乘法游戏是在一行牌上进行的。每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，所以不允许拿第1张和最后1张牌。最后一次移动后，这里只剩下两张牌。目标是使得得分的和最小。

例如，如果数是10、1、50、20、5，依次拿1、20、50，总分是10×1×50+50×20×5+10×50×5=8000；而50、20、1，总分是1×50×20+1×20×5+10×1×5=1150。

输入

第一行一个整数n，表示牌数。

第二行包括n个1~100的整数，每两个数之间用一个空格分开。

输出

一行一个整数，表示最小得分。

Input1

6
10 1 50 50 20 5

Output1

3650

感谢！