#1100. 2-05F. zzj & liaoy の 毁灭打击

正当 zzj 和 liaoy 着手准备魔法仪式的时候，突然远处出现了一大队坦克准备对他们的魔法仪式进行干扰。愤怒的 zzj 找来了可爱又强大的 qz ，试图对带有敌意的坦克群进行毁灭打击。

敌方的坦克群呈横向长条阵型，每次 qz 可以发动一个神秘技能，吃掉这些坦克中的一个，并且给其两边相邻的坦克造成极大的精神冲击。目前已知的情报是敌方的每一个坦克都有一个萌新值，每当一个坦克被吃掉时，敌方会受到数值等同于其两边坦克的萌新值乘积的精神伤害（若一侧不存在坦克，视萌新值为 $1$）。

现在 zzj 想知道 qz 按照什么样的顺序去吃这些坦克，能够使得造成总的精神伤害最高。

第一行包含一个整数 $n$ ，表示敌方坦克的数量。

接下来 $n$ 个整数，按顺序给出了敌方坦克的萌新值。

输出一个整数，表示能够对敌方造成的最大的精神伤害。

样例输入1

3
1 2 3

样例输出1

7

样例输入2

3
3 1 2

样例输出2

10

$1 \leq n \leq 300$

$1 \leq 萌新值 \leq 10000$

Hint

对于样例1，按照 $(2, 1, 3)$ 的顺序来吃，造成的精神伤害为 $(1*3), (1*3), (1*1)$ ，总共是 $7$ 。

对于样例2，按照 $(1, 2, 3)$ 的顺序来吃，造成的精神伤害为 $(3*2), (3*1), (1*1)$ ，总共是 $10$ 。