Background

学校游园活动中有 N 个游戏项目排成一条直线，每个游戏项目都有开始积分值和结束积分值两个数值。这些积分值都是正整数。对于相邻的两个游戏项目，前一个项目的结束积分值必须等于后一个项目的开始积分值，这样才能完成积分的顺畅传递。

当两个相邻游戏项目进行积分传递时，会产生欢乐值，计算公式为：前项目开始值 × 前项目结束值 × 后项目结束值。传递后，两个游戏项目的积分会合并，形成一个积分区间，其开始积分值为前项目的开始值，结束积分值为后项目的结束值。

现在有 N 个游戏项目排成一条直线，需要设计一个传递顺序，使得整个传递过程产生的总欢乐值最大。

Format

Input

第一行是一个正整数 N（2≤N≤100），表示游戏项目的数量。 第二行是 N+1 个用空格隔开的正整数，所有的数均不超过 1000。第 i 个数为第 i 个游戏项目的开始积分值（1≤i≤N），第 i 个游戏项目的结束积分值等于第 i+1 个游戏项目的开始积分值。

Output

一个正整数 E（E≤2.1×10⁹），为一个最优传递顺序所产生的总欢乐值。

Samples

4
2 3 5 10 2

710

【解释说明】 4个游戏项目的(开始值,结束值)依次为：(2,3)(3,5)(5,10)(10,2)

最优传递顺序：(((项目4⊕项目1)⊕项目2)⊕项目3) 计算过程：

项目4⊕项目1：10×2×3=60

(项目4⊕项目1)⊕项目2：10×3×5=150

(((项目4⊕项目1)⊕项目2)⊕项目3)：10×5×10=500 总欢乐值：60+150+500=710

Limitation

1s, 1024KiB for each test case.