P11958 「ZHQOI R1」划分

**请注意本题特殊的空间限制。**

给定一个长度为 $n$ 的序列 $a$，你需要将 $a$ 划分成若干个非空连续子段。 对于每个子段 $[l,r]$，定义其贡献 $w=(\min_{i=l}^{r}a_i)\times(\max_{i=l}^{r}a_i)$。你需要找出一种划分方式，使 $\sum w$ 的值最小，输出这个最小值。

第一行一个整数 $n$。 第二行 $n$ 个整数，代表数列中的数。

一行一个数，代表答案。

**【样例 1 解释】** 划分方案: $ -1 $ $ 2 $ $ \bigg| $ $ -1 $ $ 2 $。 **【样例 2 解释】** 划分方案: $ -3 $ $ 4 $ $ \bigg| $ $ -9 $ $ 1 $ $ 2 $ $ 4 $。 **【数据范围】** **本题采用捆绑测试。** 对于 $100\%$ 的数据， $1 \le n \le 10^6$，$-10^6 \le a_i \le 10^6$。 | 子任务编号 | $n\leq$ | 特殊性质 | 分值 | | :-: | :-: | :-: | :-: | | $1$ | $500$ | 无 | $5$ | | $2$ | $5000$ | 无 | $10$ | | $3$ | $10^5$ | 保证 $a_i$ 正负性相同 | $5$ | | $4$ | $10^5$ | 保证 $a_i\in\{-1,0,1\}$ | $10$ | | $5$ | $10^5$ | 保证 $a_i$ 随机生成 | $10$ | | $6$ | $10^5$ | 无 | $15$ | | $7$ | $10^6$ | 保证 $a$ 中负数个数小于 $2000$ 个 | $15$ | | $8$ | $10^6$ | 无 | $30$ |