题目描述

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

输入格式

输入的第一行包含卡片数量 N（3≤N≤100）。 第二行包含1到100之间的N个整数，用空格分隔。

输出格式

输出必须包含一个整数，即最小分数。

6
10 1 50 50 20 5

3650