配点 : $400$ 点

問題文

左右方向一列に $N$ 個のマスが並んでいます。左から $i$ 番目のマスをマス $i$ と呼ぶことにします。 この $N$ 個のマスのうち、マス $A_1$, マス $A_2$, マス $A_3$, $\dots$, マス $A_M$ の $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$

出力

最小で何回ハンコを使用すれば白色のマスが存在しない状態にすることができるかを表す整数を出力せよ。

5 2
1 3

3

$k$ として $1$ を選び、$3$ つある白色マスを一回に一つずつ赤色に塗り替えると $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$ 回も使わなくてよいです。

1 0

1

$M = 0$ の可能性もあります。