{"raw_statement":[{"iden":"problem statement","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?"},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"5 2\n1 3"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"13 3\n13 3 9"},{"iden":"sample output 2","content":"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."},{"iden":"sample input 3","content":"5 5\n5 2 1 4 3"},{"iden":"sample output 3","content":"0\n\nIf there is no white square from the beginning, we do not have to use the stamp at all."},{"iden":"sample input 4","content":"1 0"},{"iden":"sample output 4","content":"1\n\n$M$ may be $0$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}