题目描述

有 $N$ 张牌，牌面值依次为 $A_1,A_2,\ldots,A_N$。每次可以任意取出一张尚未取出的牌。取出时所得分数为该牌面值与它当前左右相邻牌面值的乘积；若一侧没有相邻牌，该侧牌面值按 $1$ 计算。取牌后，这张牌从序列中删除。

请计算所有牌取完时可能得到的最高总分。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出一个整数，表示最高总分。

样例

4
3 1 2 4

46

数据范围与提示

• $1\le N\le300$
• $1\le A_i\le100$