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 others are white. ($M$ may be $0$, in which case there is no blue square.)  
You 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.  
At 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?

Input is given from Standard Input in the following format:

```
$N$ $M$
$A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots \hspace{5pt} A_M$
```

Print the minimum number of uses of the stamp needed to have no white square.

-   $1 \le N \le 10^9$
-   $0 \le M \le 2 \times 10^5$
-   $1 \le A_i \le N$
-   $A_i$ are pairwise distinct.
-   All values in input are integers.

3

If we choose k=1 and repaint the three white squares one at a time, three uses are enough, which is optimal.
Choosing 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.

6

One optimal strategy is choosing k=2 and using the stamp as follows:

• Repaint Squares 1,2 red.
• Repaint Squares 4,5 red.
• Repaint Squares 5,6 red.
• Repaint Squares 7,8 red.
• Repaint Squares 10,11 red.
• Repaint Squares 11,12 red.

Note that, although the k consecutive squares chosen when using the stamp cannot contain blue squares, they can contain already red squares.

0

If there is no white square from the beginning, we do not have to use the stamp at all.

1

M may be 0.