题目描述

$N$ 个顶点的凸多边形 [顶点顺序为1->N]，各顶点权值已知，要求划分成 $N-2$ 个三角形，使各三角形顶点权值乘积之和为最小。

当 $n=4$，各顶点的权值分别为 $10,5,7,6$ 时，所求最小值为 $10*5*6+5*6*7=510$。

输入格式

第一行：一个整数 $n$。

第二行：$n$ 个整数,依次表示各顶点的权值。

输出格式

一个整数表示最小的乘积之和。

4
10 5 7 6

510

数据范围

$n \le 200$，所有输入数据均 $\le 1000$，所求得的最小值小于 $10^9$。