该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

乘法游戏是在一行纸牌上进行的。每一张纸牌包括了一个正整数。在每一次游戏中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数字，不允许拿第一张和最后一张，最后一次游戏后只剩下两张纸牌。编程计算最小的和值。

输入格式

第一行一个整数$\red{n（3≤n≤100）}$,纸牌的张数。第二行包括$\red{n}$个$\red{1\sim100}$的整数。

输出格式

最小得分。

样例

输入样例

6
10 1 50 50 20 5

输出样例

3650