問題文

円形のケーキがあります。円周上には $2N$ 個の点が等間隔に並んでおり、時計回りに $1, 2, \dots, 2N$ と番号付けられています。 また、 番号が奇数であるような $K$ 個の点 $A_1, A_2, \dots, A_K$ の位置にはいちごが乗っています。

これから、番号が偶数であるような頂点を $K$ 個選んで、円の中心から選んだ頂点に向かう半直線に沿ってケーキを切断し $K$ 個のピースに分割します。

どのピースにも必ずいちごが $1$ つ以上乗っているように切断する点を選んだとき、最も小さいピースの大きさの最大値を求めてください。 具体的には、選んだ頂点を番号の小さい順に $B_1, B_2, \dots, B_K$ として、$\displaystyle\min_{i=1,2,\dots,K} (B_{i+1} - B_i)$ （ただし、$B_{K+1} = B_1 + 2N$ とみなします）の最大値を求めてください。

なお、問題文の制約から条件を満たすような切り分けの方法が必ず1つは存在することが証明できます。

入力

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_K$

制約

• $2 \le K \le N \le 5 \times 10^5$
• $1 \le A_1 \lt A_2 \lt \dots \lt A_K \le 2N-1 \quad (1 \le i \le K)$
• $i=1,2,\dots,K$ について $A_i$ は奇数
• 入力は全て整数

出力

答えを $1$ 行で出力せよ。

サンプル

サンプル1

入力サンプルをコピー

入力

6 3
1 7 11

出力

4

点 $4$、点 $8$、点 $12$ の位置に切り込みを入れることで、全てのピースの大きさを $4$ にすることができます。

2 2
1 3

2

20 5
7 9 17 21 31

6