问题描述

有N张卡片摆成一行，每张卡片都包含一个正整数。在移动过程中，玩家从该行中取出一张卡片，得分等于所取卡片上的数字与其左右两侧卡片上数字的乘积。不充许取出该行中的第一张和最后一张卡片。最后一步之后，这一行只剩下两张卡片。目标是按照一定的顺序抽取卡片，使总得分最少。 例如，如果行中的卡片包含数字10 1 50 20 5，玩家可能会拿1、20和50的卡片，得分：10150+50205+10505=500+5000+2500=8000。 如果他按照相反的顺序拿卡片，即50，然后是20，然后是1，分数是：15020+1205+1015=1000+100+50 = 1150。

Input

两行。第一行为一个正整数n，表示原来卡片总数。第二行是n个整数，任何两个数之间用一个空格分隔，表示卡片上的数字（都是正整数）。

输出

最小得分

Samples

6
10 1 50 50 20 5

3650

Limitation

1s, 1024KiB for each test case.