题目描述

There is a circular pond with a perimeter of $K$ meters, and $N$ houses around them.

The $i$-th house is built at a distance of $A_i$ meters from the northmost point of the pond, measured clockwise around the pond.

When traveling between these houses, you can only go around the pond.

Find the minimum distance that needs to be traveled when you start at one of the houses and visit all the $N$ houses.

有一个周长为 $K$ 米的圆形池塘，周围有 $N$ 座房子。

按顺时针方向环绕池塘测量， $i$ -th 房屋建在距离池塘最北端 $A_i$ 米的地方。

在这些房子之间穿行时，只能绕着池塘走。

求从其中一栋房子出发，走遍所有 $N$ 栋房子所需的最小距离。

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印当你从其中一间房屋出发并访问所有 $N$ 房屋时需要走过的最小距离。

样例 #1

样例输入 #1

20 3
5 10 15

样例输出 #1

10

样例 #2

样例输入 #2

20 3
0 5 15

样例输出 #2

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$
• 所有输入值均为整数。

样例 $1$ 解释

如果你从 $1$ -st房子开始，依次前往 $2$ -nd和 $3$ -rd房子，总路程为 $10$ 。

样例 $2$ 解释

如果你从 $2$ （nd）号房屋开始，依次前往 $1$ （st）号和 $3$ （rd）号房屋，总路程为 $10$ 。