题目描述

有 $n$ 个数字 $a_1,a_2,…,a_n$，我们要把除了 $a_1,a_n$ 之外的其他数字删除，删除一个数字的代价是它乘上它相邻两个还没有被删除的数字的值，请求出最小代价是多少。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数 $a_1,a_2,…,a_n$。

输出格式

一个整数，表示答案。

Samples

5
5 6 4 2 7

178

数据规模

对于所有数据，保证 $1≤n,a_i≤500$。