AT_abc160_c [ABC160C] Traveling Salesman around Lake

题目描述

有一个周长为 $K$ 米的圆形湖，湖周围有 $N$ 户人家。

第 $i$ 户人家位于从湖的北端顺时针方向 $A_i$ 米的位置。

只能沿着湖的周围在各个房屋之间移动。

请你求出，从任意一户人家出发，访问所有 $N$ 户人家的最短移动距离。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

输出从任意一户人家出发，访问所有 $N$ 户人家的最短移动距离。

样例 1

输入

20 3
5 10 15

输出

10

样例 2

输入

20 3
0 5 15

输出

10

说明/提示

限制条件

• $2 \leq K \leq 10^6$
• $2 \leq N \leq 2 \times 10^5$
• $0 \leq A_1 < ... < A_N < K$
• 输入中的所有值均为整数。

样例解释 1

从第 $1$ 户人家出发，依次前往第 $2$ 户和第 $3$ 户，总移动距离为 $10$。

样例解释 2

从第 $2$ 户人家出发，依次前往第 $1$ 户和第 $3$ 户，总移动距离为 $10$。

由 ChatGPT 4.1 翻译