P8382 [POI 2004] Game

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.

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 the number of $\text{winning}$ moves available to the first player.

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