数轴游戏

题目描述

使用一条数轴和 $N$ 个棋子进行单人游戏。

一开始,把每个棋子分别放在任意一个整数坐标上。

此时,多个棋子可以放在同一个坐标上。

目标是反复进行下面的移动,让 $M$ 个地点(坐标 $X_1, X_2, ..., X_M$)全部被某个棋子访问到。

移动: 选 $1$ 个棋子,设其坐标为 $x$。把该棋子移动到坐标 $x+1$ 或坐标 $x-1$。

注意,棋子最初放置的坐标视为该时刻已被访问。

请计算达成目标前所需移动次数的最小值。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$X_1$ $X_2$ $...$ $X_M$

输出格式

输出达成目标前所需移动次数的最小值。

样例

2 5
10 12 1 2 14

5

按照下面的步骤移动 $5$ 次即可达成目标,这是最少次数。

• 一开始把 $2$ 个棋子分别放在坐标 $1$ 和坐标 $10$。
• 把坐标 $1$ 的棋子移动到坐标 $2$。
• 把坐标 $10$ 的棋子移动到坐标 $11$。
• 把坐标 $11$ 的棋子移动到坐标 $12$。
• 把坐标 $12$ 的棋子移动到坐标 $13$。
• 把坐标 $13$ 的棋子移动到坐标 $14$。

3 7
-10 -3 0 9 -100 2 17

19

100 1
-100000

0

数据范围

• 输入均为整数。
• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $-10^5 \leq X_i \leq 10^5$
• $X_1, X_2, ..., X_M$ 各不相同。