题目描述

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

输入格式

输入第一行一个正整数 $n$ ；

第二行 $n$ 个正整数，为各端点的权值。

输出格式

一个正整数，为最小的乘积之和。

数据范围

$N \le 50$,每个顶点的权值小于 $500$

样例

5
121 122 123 245 231

12214884