P15252 [NOSOI R1] Square Sequence

> 你知道吗？一个数的平方根的平方是它本身。

给定一个长度为 $n$ 的整数序列 $S$，将其划分为两个不交的子序列 $A$ 和 $B$（即 $A$ 和 $B$ 的并集为 $S$，交集为空。且 $A$ 和 $B$ 中元素的相对顺序与在 $S$ 中相同）。 **注意，子序列不要求连续。** 定义子序列 $X$ 的权值 $f(X)$ 为其相邻元素差的平方之和： 若 $X = [x_1, x_2, \dots, x_k]$，则 $f(X) = \sum_{i=2}^k (x_i - x_{i-1})^2$。 特别地，若 $X$ 的长度小于 $2$，则 $f(X) = 0$。 令总权值为 $f(A) + f(B)$。 求所有划分方案中最小总权值。

第 $1$ 行 $1$ 个整数 $n$，表示序列 $S$ 的长度。 第 $2$ 行 $n$ 个整数 $S_1, S_2, \dots, S_n$，表示序列 $S$。

输出 $1$ 行 $1$ 个整数，表示最小总权值。

#### 数据范围 **本题使用捆绑测试** |$\text{sid}$|$pts$|$n$|**特殊性质**| |:-------|:--------|:--------|:--------| |$1$|$10$|$\leq 18$|无| |$2$|$10$|$\leq 5\times 10^3$|有| |$3$|$20$|$\leq 5\times 10^3$|无| |$4$|$20$|$\leq 5\times 10^4$|无| |$5$|$20$|$\leq 2\times 10^5$|无| |$6$|$20$|$\leq 1\times10^6$|无| 特殊性质：保证 $\forall1\leq i