U522972 三角剖分
题目描述
你有一个凸的 $n$ 边形，其每个顶点都有一个整数值。给定一个整数数组 $a$，其中 $a_i$ 是第 $i$ 个顶点的值（按顺时针顺序）。
假设将多边形剖分（参考样例解释）为 $n - 2$ 个三角形。对于每个三角形，该三角形的值是三个顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 $n - 2$ 个三角形的值之和。
计算多边形进行三角剖分后可以得到的最低分。
输入格式
第一行一个整数 $n$。
第二行 $n$ 个整数 $a_i$。
输出格式
输出一个整数，表示将给出的多边形按三角剖分能得到的最小的值。
说明/提示
**【样例 $1$ 解释】**
**【样例 $2$ 解释】**
**【样例 $3$ 解释】**
- 对于 $100\%$ 的数据，保证 $n,a_i \le 100$。