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

这种扑克的玩法如下：

1. 玩家不能改变拿到牌的先后顺序。

2. 玩家每次可以任意出一张牌，出牌得分为：出牌的牌面值 \times 左侧相邻牌的牌面值 \times 右侧相邻牌的牌面值。如果准备出的牌左侧没有牌，则左侧牌面值视为 1，如果准备出的牌右侧没有牌，则右侧牌面值视为 1。

3. 玩家每出一张牌之后，这张牌从手中移除，并计算出牌得分。玩家最后的总得分为每次出牌得分之和。

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

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

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

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

样例 1 说明

对于牌面 [3, 1, 2, 4]，一种可以获得最高得分 46 的出牌顺序如下：

1. 先出牌面值为 1 的牌

   • 初始牌面为 [3, 1, 2, 4]。
   • 出牌 1 时，其左右相邻牌分别为 3 和 2，得分为 3 \times 1 \times 2 = 6。
   • 出牌后，手牌更新为 [3, 2, 4]。

2. 再出牌面值为 2 的牌

   • 当前牌面为 [3, 2, 4]。
   • 出牌 2 时，其左右相邻牌为 3 和 4，得分为 3 \times 2 \times 4 = 24。
   • 出牌后，牌面更新为 [3, 4]。

3. 接着出牌面值为 3 的牌

   • 现在牌面为 [3, 4]。
   • 出牌 3 时，左侧没有牌（记作 1），右侧为 4，得分为 1 \times 3 \times 4 = 12。
   • 出牌后，牌面剩下 [4]。

4. 最后出牌面值为 4 的牌

   • 仅剩牌 4，左右均无牌（均记作 1），得分为 1 \times 4 \times 1 = 4。

总得分为： 6 + 24 + 12 + 4 = 46。

数据范围

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

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

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

月赛区间DP25年4月