Gromozeka plays a single player game using a number line and
N tiles. Each of the chips is located in some integer coordinate. Note that multiple tiles can be placed at the same coordinate.
Goal of the game: to visit with chips all
M coordinates
X1,
X2, ...,
XM by repeating the next move.
Move: select a token with coordinate
X. Place this token at
X+1 or
X-1.
Please note that the coordinates where we originally placed the chips are already considered visited.
Find the minimum number of moves required to reach the goal.
Input
In the first line, the program receives two integers as input:
N and
M (1 <= N, M <= 10
5). The second line contains
M integers
X1,
X2, . ..,
XM (-10
5 <= X
i <= 10
5). All numbers
Xi are distinct.
Imprint
Display the answer to the problem.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
2 5
10 12 1 2 14
| 5 |
The goal can be reached in five moves as follows, and this is the minimum required number of moves.
First place two chips at coordinates 1 and 10.
Move the chip with coordinate 1 to 2.
Move the chip with coordinate 10 to 11.
Move the chip with coordinates 11 to 12.
Move the chip with coordinates 12 to 13.
Move the chip at coordinates 13 to 14. |
| 2 |
3 7
-10 -3 0 9 -100 2 17 |
19 |
|
| 3 |
100 1
-100000 |
0 |
|