D - 印章

得分：400分

题目描述

有N个方块从左到右排列在一行中，假设方块i是从左边起数的第i个方块。 这些方块当中的M个，分别为方块$A_1$、$A_2$、$A_3$、…、$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解释

如果我们选择$k = 1$，并且连续三次将三个白方块涂成红方块，则用三次即可，这是最优的选择方式。选择$k = 2$或更大的k将会导致无法将方块2涂成红色，因为$k$个方块不能包含蓝色方块。

样例2解释

一个最佳策略是选择$k = 2$并且用印章进行以下操作：

• 把方块1和方块2涂成红色。
• 把方块4和方块5涂成红色。
• 把方块5和方块6涂成红色。
• 把方块7和方块8涂成红色。
• 把方块10和方块11涂成红色。
• 把方块11和方块12涂成红色。 注意，当选择使用印章时，连续的k个方块不能包含蓝色方块，但是可以包含已经涂成红色的方块。

样例3解释

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

样例4解释

$M$可能为$0$。