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

内存限制:512 MiB 时间限制:750 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: foreyes1001

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例

样例输入1

3
1 2 3

样例输出1

7

样例输入2

3
3 1 2

样例输出2

10

数据范围与提示

Hint

对于样例1,按照 的顺序来吃,造成的精神伤害为 ,总共是

对于样例2,按照 的顺序来吃,造成的精神伤害为 ,总共是