题目背景

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

题目描述

给定一个长度为 $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$ 个整数，表示最小总权值。

5
1 3 2 4 5

3

5
1 2 1 2 1

0

6
1 3 1 4 2 2

2

见 ex_sequence1.in/.ans
这个样例满足 sub1 的约束条件

见 ex_sequence2.in/.ans
这个样例满足 sub3 的约束条件

见 ex_sequence3.in/.ans
这个样例满足 sub5 的约束条件

提示

数据范围

本题使用捆绑测试

$\text{sid}$	$pts$	$n$	特殊性质
$1$	$10$	$\leq 18$	无
$2$		$\leq 5\times 10^3$	有
$3$	$20$		无
$4$		$\leq 5\times 10^4$
$5$		$\leq 2\times 10^5$
$6$		$\leq 1\times10^6$

特殊性质：保证 $\forall1\leq i<n$ 有 $S_i\leq S_{i+1}$。

对于所有数据，保证 $1 \le n,a_i \le 1\times 10^6$。