题目描述

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

输入格式

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

输出格式

最小得分。

样例

输入样例

6
10 1 50 50 20 5

输出样例

3650