「LibreOJ β Round #3」绯色 IOI（开端）

题目描述

激动人心的日子终于到了。这天，他们坐上了奔向考场的列车。夕阳下绯色的天空，衬着纯黑的目送者的剪影，成为了列车消失前最后的背景。

列车徐徐行驶，Rlc 望着 Jsp，欲言又止。但她知道 Jsp 对 OI 以外的东西总是一副冷冰冰的样子，于是找来了一道旅行商问题：

给定完全图 $G=(V,E)$，每个点 $v\in V$ 有一个权值 $w_v\in\mathbb{Z}$，边 $e=(u,v)\in E$ 的长度 $w_e$ 定义为 $w_e=(w_u-w_v)^2$。

现要求一条 $G$ 中的哈密顿回路 $C$，要求经过 $V$ 中的各个点恰好一次，且回路的长度 $w(C)$ 最小。回路 $C$ 的长度 $w(C)$ 定义为 $C$ 经过的所有边的长度之和，即

$$w(C)=\sum_{e\in E(C)}w_e$$

你只需输出最小的 $w(C)$ 值。

输入格式

输入第一行包含一个正整数 $n$，表示 $|V|$。设 $V=\{1,2,\cdots,n\}$。

第二行包含 $n$ 个��空格分隔的整数，表示 $w_1,w_2,\cdots,w_n$。

输出格式

输出仅一行，包含一个整数，表示最小的 $w(C)$ 值。

样例 1

输入

4
1 2 3 4

输出

10

说明

令回路 $C:1\rightarrow 3\rightarrow 4\rightarrow 2\rightarrow 1$，则回路长度为

$$w(C)=(w_1-w_3)^2+(w_3-w_4)^2+(w_4-w_2)^2+(w_2-w_1)^2=2^2+1^2+2^2+1^2=10 $$

可以证明这是最小的 $w(C)$ 值。

数据范围与提示

对于所有数据，满足 $2\le n\le 100,000$，$-10^9\le w_v\le 10^9$。

Subtask #	分值	$n$	$|w_v|$
1	$10$	$\le 10$	$\le 10^3$
2		$\le 15$
3		$\le 20$
4	$20$	$\le 100$
5		$\le 2,000$	$\le 10^6$
6	$30$	$\le 100,000$	$\le 10^9$