Stamp

AtCoder

IDabc185_d

Time2000ms

Memory256MB

Difficulty—

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? ## Constraints * $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. ## Input 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$ [samples]

Samples

Input #1

5 2
1 3

Output #1

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.

Input #2

13 3
13 3 9

Output #2

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.

Input #3

5 5
5 2 1 4 3

Output #3

0

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

Input #4

1 0

Output #4

1

$M$ may be $0$.

API Response (JSON)

{
  "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 other...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments