4802 - 凸多边形划分
Time Limit : 1 秒
Memory Limit : 128 MB
给定一个具有 N 个顶点的凸多边形，将顶点从 1 至 N 标号，每个顶点的权值都是一个正整数。
将这个凸多边形划分成 N−2 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。
Input
第一行包含整数 N，表示顶点数量。
第二行包含 N 个整数，依次为顶点 1 至顶点 N 的权值。
Output
输出仅一行，为所有三角形的顶点权值乘积之和的最小值。
Examples
Input
5 121 122 123 245 231
Output
12214884
Hint
数据范围 N≤50, 数据保证所有顶点的权值都小于10^9