Problem Description

Let us consider a game played on an $m \times 1$ board, whose cells are numbered from $1$ to $m$.

There are $n$ pieces on the board. Each piece occupies exactly one cell, and no piece occupies cell $m$.

Each move follows these rules: the player chooses one piece and moves it to the first unoccupied cell with a larger index than its current cell. The two players move alternately. The first player to occupy cell $m$ wins.

We say that a move by the current player is a $\text{winning}$ move if, after making this move, the other player cannot win no matter what they do.

We want to know how many first moves of the first player are $\text{winning}$ moves.

Input Format

The first line contains two integers $m, n$.

The next line contains $n$ strictly increasing integers, representing the indices of the initially occupied cells.

Output Format

Output the number of $\text{winning}$ moves available to the first player.

5 2
1 3

1

Hint

For $100\%$ of the testdata: $2 \le m \le 10^{9}$, $1 \le n \le 10^{6}$, and $n + 1 \le m$.

Here is an example:

When $m = 7$, a player can move $2$ to $4$, move $3$ to $4$, or move $6$ to $7$.

Translated by ChatGPT 5