题目描述

有 $N$ 个方块从左到右排列着。设第 $i$ 个方块是从左起的第 $i$ 个方块。
其中，$M$ 个方块 $A_1$, $A_2$, $A_3$, $\\ldots$, $A_M$ 是蓝色的，其他方块是白色的（当 $M = 0$ 时，没有蓝色方块）。
你需要选择一个正整数 $k$，并制作一个宽度为 $k$ 的印章。在使用一次宽度为 $k$ 的印章时，你可以选择 $N$ 个方块中的 $k$ 个连续方块将其重新涂成红色，前提是这 $k$ 个方块不包含蓝色方块。
在选择最佳的 $k$ 和使用印章的情况下，至少需要使用印章多少次才能使没有白色方块？

约束条件

• $1 \le N \le 10^9$
• $0 \le M \le 2 \times 10^5$
• $1 \le A_i \le N$
• $A_i$ 两两不相等。
• 输入中的所有值均为整数。

输入

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

$N$ $M$ $A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_M$

输出

输出使用印章的最少次数以消除白色方块。

示例输入 1

5 2
1 3

示例输出 1

3

如果选择 $k = 1$，一个一个地重新涂上红色，则需要三次操作就足够了，这是最优的。
如果选择 $k = 2$ 或更大，由于要求 $k$ 个方块不能包含蓝色方块，所以方块$2$将无法重新涂成红色。

示例输入 2

13 3
13 3 9

示例输出 2

6

一种最佳策略是选择 $k = 2$ 并按以下方式使用印章：

• 重新涂红方块 $1, 2$。
• 重新涂红方块 $4, 5$。
• 重新涂红方块 $5, 6$。
• 重新涂红方块 $7, 8$。
• 重新涂红方块 $10, 11$。
• 重新涂红方块 $11, 12$。

请注意，当使用印章时，所选的连续 $k$ 个方块不能包含蓝色方块，但可以包含已经被涂红的方块。

示例输入 3

5 5
5 2 1 4 3

示例输出 3

0

如果一开始就没有白色方块，那么根本不需要使用印章。

示例输入 4

1 0

示例输出 4

1

$M$ 可以为 $0$。