问题描述

高桥铁路中，由于$N$节编组的火车的一部分发生了故障，因此需要$M$名维修师进行检查。

第$i$名维修师最初位于第$X_i$节车辆上。每个维修师可以检查当前所在的车辆，并且可以移动到相邻的车辆上。检查车辆不需要时间，但是移动到相邻车辆需要1分钟。

当至少有一名维修师检查了所有车辆时，检查工作将结束。请问最短需要多少时间才能完成检查工作。

输入

输入以以下格式从标准输入中给出：

$N$ $M$

$X_1$

$X_2$

:

$X_M$

• 第一行包含两个整数$N (1\leq N \leq 10^9)$和$M (1\leq M \leq 10^5, M \leq N)$，以空格分隔。表示火车由$N$节车辆组成，有$M$名维修师。
• 接下来的$M$行给出了每个维修师的信息。其中第$i (1\leq i \leq M)$行包含一个整数$X_i (1\leq X_i \leq N)$，表示第$i$名维修师最初在第$X_i$节车辆上。保证$X_i$互不相同。维修师的信息按照与第一个车辆接近的顺序给出，即$X_j < X_{j+1} (1 \leq j \leq M-1)$。

部分得分

本问题设置了部分得分。

• 若满足$N \leq 100$的数据集获得正确答案，则可得20分。
• 若满足$N \leq 500,000$的数据集获得正确答案，将额外获得60分。
• 若在没有额外限制的数据集上获得正确答案，将额外获得20分。

输出

请以分钟为单位，在一行中输出检查工作所需的最少时间。输出末尾包含换行符。

输入示例1

17 5
1
5
10
15
16

输出示例1

3

按照下图所示，维修师可以移动，仅需3分钟即可完成检查工作。

输入示例2

66 10
8
9
16
23
37
47
51
52
53
64

输出示例2

8