当前没有测试数据。

题目描述

数学课上，小A老师为每位同学发了 $N$ 张特制的扑克牌，每张牌的牌面值都在 $[1, 100]$ 之间。小A老师告诉大家，这是他发明的"数学扑克"。

这种扑克的玩法如下：

• 玩家不能改变拿到牌的先后顺序。
• 玩家每次可以任意出一张牌，出牌得分为：出牌的牌面值 $×$ 左侧相邻牌的牌面值 $×$ 右侧相邻牌的牌面值。如果准备出的牌左侧没有牌，则左侧牌面值视为 $1$，如果准备出的牌右侧没有牌，则右侧牌面值视为 $1$。
• 玩家每出一张牌之后，这张牌从手中移除，并计算出牌得分。玩家最后的总得分为每次出牌得分之和。

请你编写程序，计算出玩家能够获得的最高总得分。

输入格式

第一行输入一个整数 $N$，表示玩家手中牌的数量。

第二行输入 $N$ 个整数，依次表示玩家拿到每张牌的牌面值。

输出格式

输出一个整数，表示玩家能够获得的最高总得分。

样例 #1

输入

4
3 1 2 4

输出

46

数据范围

对于 $20\%$ 的数据，满足 $1 \le N \le 20$，且玩家拿到的 $N$ 张牌的牌面值严格单调递增。

对于 $60\%$ 的数据，满足 $1 \le N \le 50$。

对于 $100\%$ 的数据，满足 $1 \le N \le 300$，每张牌的面值均在 $[1, 100]$ 范围内。