题目描述

给定 $N$ 个整数 $a_1, a_2, \ldots, a_N$。小虾君想要将它们全部改写成相同的整数。每个 $a_i\ (1 \leq i \leq N)$ 最多只能被改写一次（也可以选择不改写）。将整数 $x$ 改写为整数 $y$ 时，需要花费的代价为 $(x-y)^2$。即使 $a_i = a_j\ (i \neq j)$，也不能用一次代价同时改写多个数（参见样例 2）。请你求出小虾君完成目标所需的总代价的最小值。

输入格式

输入以如下格式从标准输入给出。

$N\ a_1\ a_2\ \ldots\ a_N$

输出格式

输出小虾君将所有数改写为相同整数所需的总代价的最小值。

样例 1

输入

2
4 8

输出

8

样例 2

输入

3
1 1 3

输出

3

样例 3

输入

3
4 2 5

输出

5

样例 4

输入

4
-100 -100 -100 -100

输出

0

说明/提示

限制条件

• $1 \leq N \leq 100$
• $-100 \leq a_i \leq 100$

样例解释 1

如果全部改写为 $6$，总代价为 $(4-6)^2 + (8-6)^2 = 8$，这是最小值。

样例解释 2

如果全部改写为 $2$，总代价为 $(1-2)^2 + (1-2)^2 + (3-2)^2 = 3$。注意每个 $a_i$ 都要单独改写，不能把两个 $1$ 一起以 $(1-2)^2$ 的代价改写。

样例解释 3

可以不改写 $4$，把 $2$ 和 $5$ 都改写为 $4$，总代价为 $(2-4)^2 + (5-4)^2 = 5$，这是最小值。

样例解释 4

即使什么都不改写，小虾君也已经达成目标，所以总代价为 $0$。

由 ChatGPT 4.1 翻译