题目描述

给定一个具有 $n$ 个顶点的凸多边形，顶点从 $1$ 到 $n$ 编号。每个顶点都有一个正整数权值 $a_i$。

现在要将这个凸多边形划分成 $n-2$ 个互不相交的三角形。一个三角形的权值为其三个顶点权值的乘积。请计算所有三角形权值之和的最小值。

输入格式

第一行包含一个整数 $n$，表示凸多边形的顶点数。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示各顶点的权值。

输出格式

输出一行一个整数，表示三角形权值和的最小值。

5
121 122 123 245 231

12214884

数据范围与提示

• $3 \le n \le 50$
• $1 \le a_i < 10^9$

来源

一本通 5.1 例 3