题目描述

给定一个具有$\red{N}$个顶点的凸多边形，将顶点从$\red{1}$至 $\red{N}$ 标号，每个顶点的权值都是一个正整数。将这个凸多边形划分成 $\red{N−2}$个互不相交的三角形，试求这些三角形顶点的权值乘积和至少为多少。

输入格式

输入第一行为顶点数$\red{N}$

第二行依次为顶点$\red{1}$至顶点$\red{N}$的权值。

输出格式

输出仅一行，为这些三角形顶点的权值乘积和的最小值。

样例

输入数据

5
121 122 123 245 231

输出数据

12214884

提示

对于$\red{100\%}$的数据，有 $\red{N≤50}$，每个点权值小于$\red{10^9}$。