题目描述

zju 1602

无聊的邪狼天天和别人玩乘法游戏,久而久之,居然练成了一身出神入化的牌技,然后....然后就没有然后了,因为没有人愿意再和他玩第二次了。

乘法游戏是用一个序列的牌来玩的,每张牌都包含一个正整数作为其分值。当玩家将 一张牌从序列中取走时,记录下这张牌与它左右两边牌的分值三者的乘积,将该乘积加入总 分。这意昧着第一张牌和最后一张牌不可被取走。取到最后,只有两张牌被留在序列中。

比如，如果牌的序列为$\red{10,1,50,20,5}$。其中$\red{10}$和$\red{5}$是不可被移动的。

现在取走“1”这张牌.则它左右的两张牌“10”和“50”将被计算,即$\red{10\times 1\times 50}$;再取走 “20”,则“50”和“5”将被记录,即$\red{50\times 20\times 5}$;再取走$\red{50}$,则“10”和“5”将被记录，即$\red{10\times 50\times 5}$。最后的得分为: $\red{10\times 1\times 50+50\times 20\times 5 + 10\times 50\times 5 = 500+5000+2500 = 8 000}$。

但用另一种方法，如先取走$\red{50}$,再取走$\red{20}$,再取走$\red{1}$,最后得分将为: $\red{1\times 50\times 20 + 1\times 20\times 5+10\times 1\times 5 = 1 000+ 100+50 = 1 150}$。

显然第二种方法要比前一种得到的总分要小。

我们的最终目标是找到一种取法使总分最小。

输入格式

共两行。

第一行,包括一个数字$\red{N(5≤N≤15)}$,表示牌的张数。

第二行,包含$\red{N}$个数,代表每张牌的分值,范围是从$\red{1}$到$\red{100}$,中间以空格分开。

输出格式

一个整数，即最小总分。

样例

输入样例

6
10 1 50 50 20 5

输出样例

3650