题目难题

乘法游戏是用一些牌来玩的，在每张牌上都有一个正整数。玩家从一行牌中取出一张牌，得分的数量等于所取牌上的数字与左右两张牌上的数字的乘积。不允许取出第一张和最后一张牌。经过最后一步后，只剩下两张牌。玩牌的目标是把得分的总数降到最低。例如，若一行牌包含数字$1$$0$、$1$、$5$$0$、$2$$0$、$5$，则若玩家先拿出一张$1$，然后拿出$2$$0$和$5$$0$的牌，得分便是$1$$0$×$1$×$5$$0$+$5$$0$×$2$$0$×$5$+$1$$0$×$5$$0$×$5$=$5$$0$$0$+$5$$0$$0$$0$+$2$$5$$0$$0$=$8$$0$$0$$0$。若他按相反的顺序拿牌，即$5$$0$、$2$$0$、$1$，则得分是$1$×$5$$0$×$2$$0$+$1$×$2$$0$×$5$+$1$$0$×$1$×$5$=$1$$0$$0$$0$+$1$$0$$0$+$5$$0$=$1$$1$$5$$0$。

输入格式

第$1$行包含牌的数量$n$ $（$$3$$≤$$n$ $≤$$1$$0$$0$$）$，第$2$行包含$1$～$1$$0$$0$的$n$ 个整数，表示牌上的数字。

输出格式

单行输出玩牌的最小分数。

样例

6
10 1 50 50 20 5

3650

来源

POJ1651