AT_abc185_d [ABC185D] Stamp

在左右方向上有 $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\ \hspace{7pt}\ A_2\ \hspace{7pt}\ A_3\ \hspace{5pt}\ \dots\ \hspace{5pt}\ A_M$

输出一个整数，表示最少需要使用多少次印章，才能使所有白色格子都被涂成红色。

### 限制条件 - $1 \leq N \leq 10^9$ - $0 \leq M \leq 2 \times 10^5$ - $1 \leq A_i \leq N$ - $A_i$ 互不相同 - 所有输入均为整数 ### 样例解释 1 选择 $k=1$，将 3 个白色格子分别用印章一次涂成红色，共需 3 次，为最优解。如果选择 $k \geq 2$，由于印章不能覆盖蓝色格子，格子 2 无论如何都无法被涂成红色。 ### 样例解释 2 例如选择 $k=2$，可以如下使用印章达到最优： - 将格子 $1,2$ 涂成红色 - 将格子 $4,5$ 涂成红色 - 将格子 $5,6$ 涂成红色 - 将格子 $7,8$ 涂成红色 - 将格子 $10,11$ 涂成红色 - 将格子 $11,12$ 涂成红色 印章每次选择的连续 $k$ 个格子不能包含蓝色格子，但可以包含已经变成红色的格子。 ### 样例解释 3 如果一开始就不存在白色格子，则一次印章都不需要使用。 ### 样例解释 4 $M=0$ 也是可能的。 由 ChatGPT 4.1 翻译