题目内容

某公路养护段沿路依次安装了 $n$ 个配电箱，从左到右编号 $1\sim n$，第 $i$ 个箱的额定功率为 $p_i$。电工必须把这 $n$ 个箱全部联调接通。

对任意一段连续配电箱 $[L,R]$（下标从 $1$ 开始），需要按照下面的规则完成该段联调，并在所有合法方案中选择总代价最小的方案。

1. 整段直通。仅当该段功率序列是单峰时可用。这里的单峰定义为：存在一个峰顶位置 $k$（$L\le k\le R$），使得从 $L$ 到 $k$ 单调不降，从 $k$ 到 $R$ 单调不升，即 $p_L\le p_{L+1}\le \cdots\le p_k$ 且 $p_k\ge p_{k+1}\ge \cdots\ge p_R$。允许相邻功率相等；峰顶可以取在区间端点，因此整段一直递增（取 $k=R$）或一直递减（取 $k=L$）也都算单峰。整段直通的代价为 $(p_L+p_R)\times (R-L+1)$。长度为 $1$ 的段视为已经接通，其最小代价规定为 $0$，不计算整段直通代价。长度为 $2$ 的段一定是单峰。
2. 中剖并网。任选一个切点 $t$（$L\le t<R$），将该段分成 $[L,t]$ 和 $[t+1,R]$ 两段。先分别按照同样的规则完成这两个子段的联调，并使每个子段的联调代价最小，再将两段并网。并网本身的代价为 $p_t\times p_{t+1}$，因此该方案的总代价为两个子段的最小联调代价之和，再加上 $p_t\times p_{t+1}$。若采用中剖并网，可以在所有合法切点 $t$ 中任选，并取总代价最小的方案。

如果一段功率序列是单峰，则既可以选择整段直通，也可以选择中剖并网，并在所有方案中取最小代价；如果不是单峰，则不能整段直通，只能通过中剖并网完成联调。

求完成整段 $[1,n]$ 联调的最小代价。

输入描述

第一行一个整数 $n$。

第二行 $n$ 个整数 $p_1,p_2,\ldots,p_n$。

约束

$1 \le n \le 200$

$1 \le p_i \le 100$

输出描述

输出一个整数：完成全部联调的最小代价。

样例1

输入

3
2 3 10

输出

32

说明

三个箱的功率为 $2,3,10$。取峰顶 $k=3$，左边 $2\le 3\le 10$，右边已无后续元素，因此整段算单峰（一直递增的特例）。

• 整段直通代价为 $(2+10)\times 3=36$。
• 在 $t=1$ 切开：左段只有 $2$，代价 $0$；右段 $3,10$ 可直通，代价 $(3+10)\times 2=26$，也可并网，代价 $3\times 10=30$，取 $26$。再付并网代价 $2\times 3=6$，合计 $32$。
• 在 $t=2$ 切开：左段 $2,3$ 的直通代价为 $(2+3)\times 2=10$，并网代价为 $2\times 3=6$，取 $6$；再付并网代价 $3\times 10=30$，合计 $36$。

最小代价为 $32$。整段虽然可以直通，但先切开再并网更便宜。

样例2

输入

4
3 1 4 2

输出

12

说明

四个箱的功率为 $3,1,4,2$。整段不是单峰，不能直通，必须切开。

在 $t=1$ 切开：左段只有 $3$，代价 $0$；右段 $1,4,2$ 是单峰（峰在 $4$），直通代价 $(1+2)\times 3=9$。并网代价 $3\times 1=3$，合计 $12$。

在 $t=2$ 切开：左段 $3,1$ 取 $\min((3+1)\times 2,\,3\times 1)=3$，右段 $4,2$ 取 $\min((4+2)\times 2,\,4\times 2)=8$，并网代价 $1\times 4=4$，合计 $15$。

在 $t=3$ 切开：左段 $3,1,4$ 不是单峰，继续切开后最小代价为 $7$，再加上并网代价 $4\times 2=8$，合计 $15$。

因此最小代价为 $12$。