C - 环状湖的旅行商问题

得分 : $300$ 分

问题描述

在一个周长为 $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$。