問題文

左右方向の長さが $L$ のようかんがあります。ようかんには $N$ 個の切れ目が付いており、左から $i$ 番目の切れ目は、ようかんの左側を始点として長さ $X_i$ の部分にあります。

AさんとBさんは、このようかんを以下の手順で分け合おうとしています。

1. $1$ 以上 $N$ 以下の奇数 $k$ を選択する。
2. $N$ 個ある切れ目から $k$ 個の切れ目を選択し、選択した切れ目でようかんを切る。
3. ようかんは $k + 1$ 個（これは偶数である）のピースに分割される。分割されたピースに対し、左から順に $1, 2, \dots, k + 1$ の番号を付ける。
4. Aさんは奇数の番号がついたピースすべてを、Bさんは偶数の番号がついたピースすべてを得る。

制約

• 入力は全て整数
• $2 \leq L \leq 10^5$
• $1 \leq N \leq 100$
• $0 \lt X_1 \lt \dots \lt X_N \lt L$

入力

入力は標準入力から以下の形式で与えられる．

$L$ $N$
$X_1$ $X_2$ $\dots$ $X_N$

サンプル

サンプル1

入力

5 2
1 3

出力

1

長さ $5$ のようかんの、左から $1, 3$ の地点に切れ目があります。 $2$ つ目の切れ目でようかんを切った時、ようかんは長さ $3, 2$ に分割されます。

このとき、Aさんが長さ $3$ のピース $1$ 、Bさんが長さ $2$ のピース $2$ を得るので、$|A - B| = 1$ となります。$|A - B|$ をこれより小さくすることはできないので、答えは $1$ です。

サンプル2

入力

9 3
1 2 7

出力

3

長さ $9$ のようかんの、左から $1, 2, 7$ の地点に切れ目があります。すべての切れ目でようかんを切った時、ようかんは長さ $1, 1, 5, 2$ の $4$ つのピースに分割されます。

Aさんはピース $1, 3$ を、Bさんはピース $2, 4$ を取ります。よって、$|A - B| = |6 - 3| = 3$ となります。$|A - B|$ をこれ以上小さくすることはできないので、答えは $3$ です。

サンプル3

入力

2 1
1

出力

0

サンプル4

入力

100000 30
3094 4822 5682 6189 6494 6505 8276 8758 9856 11633 14312 16150 16304 20183 22646 23645 24327 25607 26464 32214 32407 33177 39608 41552 42802 44344 44706 45451 49184 97259

出力

1632