問題文

$1$ 周 $K$ メートルの円形の湖があり、その周りに $N$ 軒の家があります。

$i$ 番目の家は、湖の北端から時計回りに $A_i$ メートルの位置にあります。

家の間の移動は、湖の周りに沿ってのみ行えます。

いずれかの家から出発して $N$ 軒すべての家を訪ねるための最短移動距離を求めてください。

制約

• $2 \\leq K \\leq 10^6$
• $2 \\leq N \\leq 2 \\times 10^5$
• $0 \\leq A_1 < ... < A_N < K$
• 入力中のすべての値は整数である。

入力

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

$K$ $N$ $A_1$ $A_2$ $...$ $A_N$

出力

いずれかの家から出発して $N$ 軒すべての家を訪ねるための最短移動距離を出力せよ。

入力例 1

20 3
5 10 15

出力例 1

10

$1$ 番目の家から出発し、$2$ 番目、$3$ 番目の家へ順に移動すると移動距離が $10$ になります。

入力例 2

20 3
0 5 15

出力例 2

10

$2$ 番目の家から出発し、$1$ 番目、$3$ 番目の家へ順に移動すると移動距離が $10$ になります。