题目内容

某公路养护段沿路依次安装了 $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$ 中任选，并取总代价最小的方案。