在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。

通过吸盘的作用，相邻两颗珠子可以聚合成一颗珠子，同时释放能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m * r * n（Mars单位），新产生的珠子的头标记为m，尾标记为n。

Mars人会不断聚合相邻珠子，直到项链上只剩下一颗珠子为止。不同的聚合顺序得到的总能量不同，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

示例说明： 设N=4，4颗珠子的头标记与尾标记依次为(2,3) (3,5) (5,10) (10,2)。用⊕表示两颗珠子的聚合操作，(j⊕k)表示第j、k两颗珠子聚合后释放的能量：

• 第4、1两颗珠子聚合后释放的能量为：(4⊕1) = 10 * 2 * 3 = 60
• 最优聚合顺序的总能量为：((4⊕1)⊕2)⊕3 = 10*2*3 + 10*3*5 + 10*5*10 = 710

输入描述： 第一行是一个正整数N（4 ≤ N ≤ 100），表示项链上珠子的个数。 第二行是N个用空格隔开的正整数，所有数值均不超过1000，依次为每颗珠子的头标记。

输出描述： 输出一个正整数E（E ≤ 2.1×10^9），表示最优聚合顺序释放的总能量。

输入样例：

4
2 3 5 10

输出样例：

710