题目描述

在一条笔直的道路上有 $N$ 只河狸。这条道路可以视为数轴，第 $i$ 只（$1 ≤ i ≤ N$）河狸位于坐标 $X_i$ 处。

由于河狸生性怕寂寞，当且仅当同一坐标存在至少一只其他河狸时，它们才会感到快乐。

现在需要通过合理移动河狸，在确保所有河狸都快乐的前提下，使它们的移动距离总和尽可能小。河狸可以不移动。

给定 $N$ 只河狸的坐标，请编写程序计算使所有河狸都快乐时，河狸移动距离总和的最小值。

可以证明本题中答案一定是整数。

输入格式

如下所示：

$N$
$X_1$ $X_2$ $\cdots$ $X_N$

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

4
1 2 3 4

输出 #1

2

输入输出样例 #2

输入 #2

5
1 9 8 2 7

输出 #2

3

输入输出样例 #3

输入 #3

10
9 20 5 10 8 1 10 19 15 4

输出 #3

10

说明/提示

样例解释

样例 $1$ 解释

第一只河狸移动到 $2$ 处，第三只河狸移动到 $4$ 处。可以证明没有更优的方案。

该样例满足所有子任务的限制。

样例 $2$ 解释

第一只河狸移动到 $2$ 处，第二只河狸和第五只河狸移动到 $8$ 处。可以证明没有更优的方案。

该样例满足子任务 $3,4$ 的限制。

样例 $3$ 解释

该样例满足子任务 $3,4$ 的限制。

数据范围

• $2\le N\le 3\times 10^5$；
• $1\le X_i\le 10^9$；
• 输入的值全部是整数。

子任务

1. （17pts） $N=4$。
2. （20pts）$\forall 1\le i\le N$，$X_i=i$。
3. （35pts）$N\le 100$；$\forall 1\le i\le N$，$X_i\le 100$。
4. （28pts）无额外限制。

翻译来自 DeepSeek-R1 并经过人工微调。