Description

无聊的邪狼天天和别人玩乘法游戏,久而久之,居然练成了一身出神人化的牌技,然后·...··然后就没有然后了,因为没有人愿意再和他玩第二次了。 乘法游戏是用一个序列的牌来玩的,每张牌都包含一个正整数作为其分值。当玩家-张牌从序列中取走时,记录下这张牌与它左右两边牌的分值三者的乘积，将该乘积加人总分。这意味着第一张牌和最后一张牌不可被取走。取到最后,只有两张牌被留在序列中，比如,如果牌的序列为 10,1,50,20,5。其中 10 和 5 是不可被移动的。 现在取走“1”这张牌,则它左右的两张牌“10”和“50”将被计算，即 10X1X50;再取走“20”,则“50”和“5”将被记录,即 50X20X5;再取走 50,则“10”和“5”将被记录,即 10X50X5。最后的得分为:10X1X50 + 50X20X5 +10X50X5 = 500+5000+2 500 =8000但用另一种方法,如先取走 50,再取走 20,再取走 1,最后得分将为:1X50X20 十 1X 20X5 +10X1X5=1000+100+50 =1150 显然第二种方法要比前一种得到的总分要小 我们的最终目标是找到一种取法使总分最小，

Format

Input

共两行。 第一行,包括一个数字 N(5 <N < 15),表示牌的张数第二行,包含 N 个数,代表每张牌的分值,范围是从 1到 100,中间以空格分开。

Output

一个整数,即最小总分。

Samples

6
10 1 50 50 20 5

3650