UOJ Logo 小司码 Online Judge

XSMOJ

第267题   乘法游戏

统计 下一题 上一题

题目描述

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

例如,如果数是10、1、50、20、5,依次拿1、20、50,总分是10x1x50+50x20x5+10x50x5=8000;而拿50、20、1,总分是1x50x20+1x20x5+10x1X5=1150。

输入格式

第1行1个整数n,表示牌数。

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

输出格式

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

样例数据

input


6

10 1 50 50 20 5

output


3650

数据规模与约定

时间限制:$1 \text{s}$

空间限制:$256 \text{MB}$