#1537. 凸多边形划分

凸多边形划分

题目描述

给定一个具有 N(3N50)N \pod {3 \le N \le 50} 个顶点(从 11NN 编号)的凸多边形,每个顶点的权均已知。问如何把这个凸多边形划分成 N2N - 2 个互不相交的三角形,使得这些三角形顶点的权的乘积之和最小?

输入

第一行:顶点数 NN

第二行:NN 个顶点(从 11NN)的权值(11100100 之间)

输出

最小的和的值。

样例

输入

5
121 122 123 245 231

输出

12214884