Description

给定一个具有N（N<=50）个顶点（从1到N编号）的凸多边形，每个顶点的权均是一个正整数。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？

Format

Input

输入文件的第一行为顶点数N；
第二行为N个顶点（从1到N）的权值。

Output

输出文件只有一行，为这些三角形顶点的权的乘积之和的最小值。

Sample 1

Input

5
121 122 123 245 231

Output

12214884

Limitation

1s, 128MiB for each test case.

Source

HNOI’97