AT_codefestival_2015_qualA_d 壊れた電車

[problemUrl]: https://atcoder.jp/contests/code-festival-2015-quala/tasks/codefestival_2015_qualA_d 高橋鉄道では、$ N $ 両編成の電車の一部が壊れてしまったため、$ M $ 人の整備士が点検をすることになりました。 $ i $ 人目の整備士ははじめ、$ X_i $ 両目の車両にいます。それぞれの整備士は、今いる車両を点検することと、隣の車両に移動することができます。車両の点検には時間はかかりませんが、隣の車両に移動するには $ 1 $ 分かかります。 全ての車両を少なくとも $ 1 $ 人の整備士が点検した状態になると点検作業は終了となります。点検作業は最短何分で終了させることができるでしょうか。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ X_1 $ $ X_2 $ : $ X_M $ - $ 1 $ 行目には、$ 2 $ つの整数 $ N\ (1\ ≦\ N\ ≦\ 10^9),\ M\ (1\ ≦\ M\ ≦\ 10^5,\ M\ ≦\ N) $ が空白区切りで与えられる。これは、電車が $ N $ 両の車両からなり、整備士が $ M $ 人いることを表す。 - $ 2 $ 行目からの $ M $ 行には、整備士の情報が与えられる。このうち $ i\ (1\ ≦\ i\ ≦\ M) $ 行目には、整数 $ X_i\ (1\ ≦\ X_i\ ≦\ N) $ が与えられる。これは、$ i $ 人目の整備士がはじめ $ X_i $ 両目の車両にいることを表す。ただし、$ X_i $ は全て相異なることが保証される。また、整備士の情報は $ 1 $ 両目の車両に近い順に与えられる、つまり $ X_j\

点検作業にかかる時間の最小値を分単位で $ 1 $ 行に出力せよ。出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 100 $ を満たすデータセットに正解した場合は、$ 20 $ 点が与えられる。 - $ N\ ≦\ 500,000 $ を満たすデータセットに正解した場合は、上記とは別に $ 60 $ 点が与えられる。 - 追加の制約のないデータセットに正解した場合は、上記とは別に $ 20 $ 点が与えられる。 ### Sample Explanation 1 下の図のように整備士が移動すれば $ 3 $ 分で点検作業を終了させることができます。 !\[figure1\](https://code-festival-2015-quala.contest.atcoder.jp/img/other/code\_festival\_2015\_quala/BrokenDensya.png)