题目背景

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

题目描述

给定一个长度为 $n$ 的序列 $a$，你需要将 $a$ 划分成若干个非空连续子段。

对于每个子段 $[l,r]$，定义其贡献 $w=(\min_{i=l}^{r}a_i)\times(\max_{i=l}^{r}a_i)$。你需要找出一种划分方式，使 $\sum w$ 的值最小，输出这个最小值。

输入格式

第一行一个整数 $n$。

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

输出格式

一行一个数，代表答案。

4
-1 2 -1 2

-4

6
-3 4 -9 1 2 4

-48

提示

【样例 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$。