题目描述

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

如果你从第一个房屋开始，按照顺序去第二个和第三个房屋，总共行走的距离将为10米。

示例输入2

20 3
0 5 15

示例输出2

10

如果你从第二个房屋开始，按照顺序去第一个和第三个房屋，总共行走的距离将为10米。