环湖旅行商

题目描述

有一个周长 $K$ 米的圆形湖泊,周围有 $N$ 栋房子。

第 $i$ 栋房子位于从湖的北端顺时针前进 $A_i$ 米的位置。

房子之间的移动只能沿着湖边进行。

请找出从某栋房子出发,访问全部 $N$ 栋房子的最短移动距离。

输入格式

输入按以下格式从标准输入给出:

$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$。

数据范围

• $2 \leq K \leq 10^6$
• $2 \leq N \leq 2 \times 10^5$
• $0 \leq A_1 \lt ... \lt A_N \lt K$
• 输入中的所有值都是整数