选取书籍

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

输入格式

第一行输入一个整数 M，为书架上一列书籍的数量。 第二行 M 个正整数，每个正整数不大于100，用空格隔开，分别表示第 i 本书籍的价格 (3≤i≤M)。

输出格式

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

4
5 3 2 9

120

数据范围

时间限制: 1000ms

内存限制: 128MB