{"problem":{"name":"Stamp","description":{"content":"There are $N$ squares arranged in a row from left to right. Let Square $i$ be the $i$\\-th square from the left.   $M$ of those squares, Square $A_1$, $A_2$, $A_3$, $\\ldots$, $A_M$, are blue; the other","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc185_d"},"statements":[{"statement_type":"Markdown","content":"There are $N$ squares arranged in a row from left to right. Let Square $i$ be the $i$\\-th square from the left.  \n$M$ of those squares, Square $A_1$, $A_2$, $A_3$, $\\ldots$, $A_M$, are blue; the others are white. ($M$ may be $0$, in which case there is no blue square.)  \nYou will choose a positive integer $k$ just once and make a stamp with width $k$. In one use of a stamp with width $k$, you can choose $k$ consecutive squares from the $N$ squares and repaint them red, as long as those $k$ squares do not contain a blue square.  \nAt least how many uses of the stamp are needed to have no white square, with the optimal choice of $k$ and the usage of the stamp?\n\n## Constraints\n\n*   $1 \\le N \\le 10^9$\n*   $0 \\le M \\le 2 \\times 10^5$\n*   $1 \\le A_i \\le N$\n*   $A_i$ are pairwise distinct.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1 \\hspace{7pt} A_2 \\hspace{7pt} A_3 \\hspace{5pt} \\dots \\hspace{5pt} A_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc185_d","tags":[],"sample_group":[["5 2\n1 3","3\n\nIf we choose $k = 1$ and repaint the three white squares one at a time, three uses are enough, which is optimal.  \nChoosing $k = 2$ or greater would make it impossible to repaint Square $2$, because of the restriction that does not allow the $k$ squares to contain a blue square."],["13 3\n13 3 9","6\n\nOne optimal strategy is choosing $k = 2$ and using the stamp as follows:\n\n*   Repaint Squares $1, 2$ red.\n*   Repaint Squares $4, 5$ red.\n*   Repaint Squares $5, 6$ red.\n*   Repaint Squares $7, 8$ red.\n*   Repaint Squares $10, 11$ red.\n*   Repaint Squares $11, 12$ red.\n\nNote that, although the $k$ consecutive squares chosen when using the stamp cannot contain blue squares, they can contain already red squares."],["5 5\n5 2 1 4 3","0\n\nIf there is no white square from the beginning, we do not have to use the stamp at all."],["1 0","1\n\n$M$ may be $0$."]],"created_at":"2026-03-03 11:01:14"}}