题目描述

有一个乘法游戏，使用一排卡片进行，每张卡片上写有一个正整数。每次操作时，玩家从这一排卡片中取出一张卡片，获得的分数等于被取出的卡片上的数字乘以其左边和右边卡片上的数字。注意，不能取走第一张和最后一张卡片。经过若干次操作后，最终只剩下两张卡片。

目标是按照某种顺序取走卡片，使得获得的总分数最小。

例如，如果卡片上的数字依次为 10 1 50 20 5，玩家可以先取走 1，然后取走 20，最后取走 50，得分如下：

$$10 \times 1 \times 50 + 50 \times 20 \times 5 + 10 \times 50 \times 5 = 500 + 5000 + 2500 = 8000$$

如果玩家按照相反的顺序取卡片，即先取 50，再取 20，最后取 1，得分将是：

$$1 \times 50 \times 20 + 1 \times 20 \times 5 + 10 \times 1 \times 5 = 1000 + 100 + 50 = 1150$$

输入格式

第一行包含一个整数 $N$（$3 \le N \le 100$），表示卡片的数量。

第二行包含 $N$ 个整数，表示每张卡片上的数字，整数之间用空格隔开。每个整数的范围是 $[1, 100]$。

输出格式

输出一个整数，表示可以获得的最小总分数。

6
10 1 50 50 20 5

3650

数据规模与约定

对于 $100\%$ 的数据，$3 \le N \le 100$，卡片上的数字满足 $1 \le a_i \le 100$。