問題文

高橋鉄道では、$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 < X_{j+1} (1 ≦ j ≦ M-1)$ であることが保証される。

部分点

この問題には部分点が設定されている。

• $N ≦ 100$ を満たすデータセットに正解した場合は、$20$ 点が与えられる。
• $N ≦ 500,000$ を満たすデータセットに正解した場合は、上記とは別に $60$ 点が与えられる。
• 追加の制約のないデータセットに正解した場合は、上記とは別に $20$ 点が与えられる。

出力

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

入力例1

17 5
1
5
10
15
16

出力例1

3

下の図のように整備士が移動すれば $3$ 分で点検作業を終了させることができます。

入力例2

66 10
8
9
16
23
37
47
51
52
53
64

出力例2

8