P11958 「ZHQOI R1」Partiton

**Please note the special memory limits for this problem.**

You are given array $ a_1, a_2, \dots, a_n $ . You need to split it into some subsegments (so every element is included in exactly one subsegment). The weight of a subsegment $ a_l, a_{l+1}, \dots, a_r $ is equal to $(\min_{i=l}^{r}a_i)\times(\max_{i=l}^{r}a_i)$ . The weight of a partition is a total weight of all its segments. Find the partition of minimal weight.

The first line contains an integer $ n $ — the length of the array $ a $ . The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ — the array $ a $ .

Print a single integer — the minimal weight among all possible partitions.

The optimal partition in the first example is next: $ -1 $ $ 2 $ $ \bigg| $ $ -1 $ $ 2 $ . The optimal partition in the second example is next: $ -3 $ $ 4 $ $ \bigg| $ $ -9 $ $ 1 $ $ 2 $ $ 4 $ . **Constraints** **This problem uses subtask scoring.** For $100\%$ of the data, $1 \le n \le 10^6$, $-10^6 \le a_i \le 10^6$. | Subtask | $n\leq$ | Additional Constraints | Score | | :-: | :-: | :-: | :-: | | $1$ | $500$ | None | $5$ | | $2$ | $5000$ | None | $10$ | | $3$ | $10^5$ | All $a_i$ have the same sign | $5$ | | $4$ | $10^5$ | $a_i \in \{-1, 0, 1\}$ | $10$ | | $5$ | $10^5$ | $a_i$ are randomly generated | $10$ | | $6$ | $10^5$ | None | $15$ | | $7$ | $10^6$ | Number of negatives in $a$ is less than $2000$ | $15$ | | $8$ | $10^6$ | None | $30$ |