Problem 7F. Node

时间限制：1s

空间限制：256MB

Description

给定数字 \(N\) ，代表一个环中结点个数。

每个结点都有头值和尾值，如果前一个结点的尾值 \(t_1\) 等于后一个结点的头值 \(h_2\) ，那么两个结点将可以合并为一个结点，并且新结点的头值 \(h_{new}\) 等于前一个结点的头值 \(h_1\) ，新结点的尾值 \(t_{new}\) 等于后一个结点的尾值 \(t_2\) ，需要花费价值为 \(h_1 \times t_1 \times t_2\) 或 \(h_1 \times h_2 \times t_2\) 。

求解最优合并顺序，使得最终花费价值总和最大。输出最大的值。

Input Format

第一行是一个正整数 \(N\)（\(4 \le N \le 100\)），表示环上结点个数。第二行是 \(N\) 个用空格隔开的正整数，所有的数均不超过 \(1000\)。第 \(i\) 个数为第 \(i\) 个结点的头值（\(1 \le i \le N\)），当 \(i<N\) 时，第 \(i\) 个结点的尾值应该等于第 \(i+1\) 个结点的头值。第 \(N\) 个结点的尾值应该等于第 \(1\) 个结点的头值。

Output Format

一个正整数 \(E\) ，为总和最大的最终花费价值。

Input Example #1：

4
2 3 5 10

Output Example #1：

710

Note

样例中 \(4\) 个结点的头与尾依次为 \((2,3)(3,5)(5,10)(10,2)\)。我们用记号 \(\oplus\) 表示两个结点的合并，\((j \oplus k)\) 表示第 \(j,k\) 两个结点合并后所花费的价值。则第 \(4\)，\(1\) 两个结点合并花费的价值：

\((4 \oplus 1)=10 \times 2 \times 3=60\)。

最终可以得到最优值的一个合并顺序所花费的价值为：

\((((4 \oplus 1) \oplus 2) \oplus 3)=10 \times 2 \times 3+10 \times 3 \times 5+10 \times 5 \times 10=710\)。