题目描述 walnut.cpp

蜗牛老师打算买$n-2$个核桃，n个核桃排成一排，第$i$个核桃有一个权值$a_i$，每次你可以选取当前核桃队列的一个核桃（不能取首尾两端的核桃），将它拿走，你需要支付的金额为：当前核桃的权值加上与他相邻的两个核桃的权值,的三次方。

假如你当前选取的核桃权值为$b$，与 他相邻的两个核桃权值是$a$,$c$，那么你需要支付的代价为 $(a+b+c)^3$。

注意：此次操作后你所选的核桃将被从队列里拿走。

蜗牛老师想要花费最蜗牛老师的代价将$n-2$个核桃买走，你能帮帮他吗。

输入：walnut.in

第一行一个整数$n$,第二行$n$个整数，第$i$个整数表示核桃的权值$a_i$。

输出：walnut.out

一行一个整数，表示蜗牛老师需要花费的最蜗牛老师代价。

对于$20\%$的数据： $n\le10$；

对于$40\%$的数据：$n\le20$；

另外$10\%$的数据：保证$a_i$都相同；

对于$100\%$的数据：$3\le n\le200,a_i\le1e3$;