配点 : $300$ 点

問題文

$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$ 軒すべての家を訪ねるための最短移動距離を出力せよ。

20 3
5 10 15

10

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

20 3
0 5 15

10

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