题目描述

一排牌上写有正整数，每次移走一张不是当前最左或最右的牌，得分为这张牌与左右紧邻两张牌的数字之积。直到只剩首尾两张牌。求总得分的最小值。

输入格式

第一行牌数 $n$。第二行 $n$ 个整数。

输出格式

输出最小总得分。

样例

6
10 1 50 50 20 5

3650

数据范围

对于30%的数据，$2\le n\le5$；对于60%的数据，$2\le n\le20$；对于100%的数据，$2\le n\le100$，$1\le a_i\le100$。