题目描述

桌面上从左到右摆放着 $N$ 张数字卡片。每次可以取走一张既不是最左端也不是最右端的卡片，得到的分数等于这张卡片的数值乘以它当时左右相邻两张卡片的数值。不断操作，直到只剩两张卡片。请计算可能得到的最小总分。

输入格式

第一行输入一个整数 $N$。

接下来输入 $N$ 个整数，按从左到右的顺序表示卡片上的数值。

输出格式

输出一个整数，表示最小总分。

数据范围与约定

$3\le N\le100$，$1\le a_i\le100$。

可见测试数据

输入数据 1

6
10 1 50 50 20 5

输出数据 1

3650

输入数据 2

5
5
3
2
3
1

输出数据 2

27

输入数据 3

5
1
2
3
4
4

输出数据 3

34