图章

题目描述

左右方向一列排着 $N$ 个格子。将从左数第 $i$ 个格子称为格子 $i$。

在这 $N$ 个格子中，格子 $A_1$、格子 $A_2$、格子 $A_3$、$\dots$、格子 $A_M$ 共 $M$ 个格子是蓝色的，其余格子是白色的。（也可能 $M = 0$，此时没有蓝色格子。）

你只能有一次机会，选择一个正整数 $k$ 制作宽度为 $k$ 的图章。使用一次宽度为 $k$ 的图章，可以在这 $N$ 个格子中选择连续 $k$ 个格子，将它们重新涂成红色。但是此时，这 $k$ 个格子中不能包含蓝色格子。

当 $k$ 和图章的使用方式都选取适当时，最少需要使用多少次图章，才能使白色格子不存在？

输入格式

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

$N$ $M$
$A_1$ $A_2$ $A_3$ $\dots$ $A_M$

输出格式

输出表示最少需要使用多少次图章才能使白色格子不存在的整数。

样例

5 2
1 3

3

选择 $k$ 为 $1$，将 $3$ 个白色格子每次涂红 $1$ 个，需要 $3$ 次即可达成目标，这是最优的。

如果选择 $k$ 为 $2$ 以上，由于使用图章时 $k$ 个格子中不能包含蓝色格子的限制，无论怎样都无法把格子 $2$ 涂成红色。

13 3
13 3 9

6

例如选择 $k = 2$，按如下方式使用图章是最优的：

• 将格子 $1, 2$ 涂成红色
• 将格子 $4, 5$ 涂成红色
• 将格子 $5, 6$ 涂成红色
• 将格子 $7, 8$ 涂成红色
• 将格子 $10, 11$ 涂成红色
• 将格子 $11, 12$ 涂成红色

使用图章时选择的连续 $k$ 个格子不能包含蓝色格子，但包含已涂成红色的格子没有问题。

5 5
5 2 1 4 3

0

如果一开始就没有白色格子，图章可以一次也不用。

1 0

1

也可能出现 $M = 0$ 的情况。

数据范围

• $1 \le N \le 10^9$
• $0 \le M \le 2 \times 10^5$
• $1 \le A_i \le N$
• 各 $A_i$ 互不相同
• 输入均为整数