AT_abc117_c [ABC117C] Streamline

[problemUrl]: https://atcoder.jp/contests/abc117/tasks/abc117_c 数直線と $ N $ 個のコマを用いて $ 1 $ 人でゲームを行います。 はじめ、これらのコマをそれぞれ好きな整数座標に置きます。 このとき、同じ座標に複数のコマを置いても構いません。 以下の移動を繰り返して、座標 $ X_1,\ X_2,\ ...,\ X_M $ の $ M $ 個の地点全てをいずれかのコマで訪れることが目的です。 **移動**: コマを $ 1 $ つ選び、そのコマの座標を $ x $ とする。そのコマを座標 $ x+1 $ もしくは座標 $ x-1 $ に移動する。 ただし、最初にコマを置いた座標はその時点で訪れたとみなします。 目的を達成するまでに移動を行う回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ X_1 $ $ X_2 $ $ ... $ $ X_M $

目的を達成するまでに移動を行う回数の最小値を出力せよ。

### 制約 - 入力はすべて整数である。 - $ 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 $ は全て異なる。 ### Sample Explanation 1 以下の手順で $ 5 $ 回移動を行うと目的を達成でき、このときが最小です。 - はじめに $ 2 $ 個のコマをそれぞれ座標 $ 1 $, 座標 $ 10 $ に置きます。 - 座標 $ 1 $ のコマを座標 $ 2 $ に移動します。 - 座標 $ 10 $ のコマを座標 $ 11 $ に移動します。 - 座標 $ 11 $ のコマを座標 $ 12 $ に移動します。 - 座標 $ 12 $ のコマを座標 $ 13 $ に移動します。 - 座標 $ 13 $ のコマを座標 $ 14 $ に移動します。