该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个具有 $N \pod {3 \le N \le 50}$ 个顶点（从 $1$ 到 $N$ 编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成 $N - 2$ 个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？

输入

第一行：顶点数 $N$

第二行：$N$ 个顶点（从 $1$ 到 $N$）的权值（$1$ 到 $100$ 之间）

输出

最小的和的值。

样例

输入

5
121 122 123 245 231

输出

12214884