选取书籍

题目描述

有个奇怪的图书馆，有 $M$ 本书籍摆成一列，每本书籍都标记有一个正整数价格。在取书过程中，读者从该列中取走一本书，需要支付所取书籍的价格与其左右两侧书籍价格的乘积。不允许取走该列中的第一本和最后一本书籍。最终步骤之后，这一列只剩下两本书籍。目标是以某种顺序取走可以取走的所有书籍，使得总支付金额最小。

输入格式

第一行输入一个整数 $M$，为书架上一列书籍的数量。

第二行 $M$ 个正整数，每个正整数不大于 $100$，用空格隔开，分别表示第 $i$ 本书籍的价格（$3 \le i \le M$）。

输出格式

输出最小支付金额是多少？

样例输入 #1

4
5 3 2 9

样例输出 #1

120

数据范围

$M$ 为正整数，每本书籍的价格为不大于 $100$ 的正整数。

知识点与难度

本题涉及的知识点从属于 GESP七级（区间DP、动态规划），难度等级：Mid+。

测试点分布