Counting Winning Moves

Consider a game played on an $m\times 1$ board whose cells are numbered from $1$ to $m$. Initially, there are $n$ pieces placed on the board (each occupying one cell) with the guarantee that no piece is in cell $m$. A move is defined as follows: the current player selects a piece and moves it to the first unoccupied cell with an index greater than its current cell. That is, if a piece is at cell $p$, it is moved to the smallest number $r>p$ such that cell $r$ is not occupied. Two players alternate moves, and the game ends immediately when a piece is moved into cell $m$ – the mover wins.

Furthermore, we call a move a ( \textit{winning} ) move if and only if after making that move the current player forces the game into a position from which the opponent has no winning strategy (i.e. no matter how the opponent plays, the current player can win eventually). In the initial configuration the first player may have several legal moves. Your task is to determine how many of these moves are ( \textit{winning} ) moves.

A useful observation is that if we denote the positions (in increasing order) by (p_1, p_2,\dots,p_n) then the only legal move for piece (i) (for (1 \le i < n)) exists if and only if [ p_i + 1 < p_{i+1}, ] while for the last piece (i.e. (i=n)) a move is legal if and only if (p_n < m).

Moreover, note that when a move is made the effect on the "remaining moves" is different depending on which piece is moved. In fact, if we define [ T = m - p_1 - (n-1), ] which is the total number of moves eventually available if every move increases a piece by exactly one (and the maximum value a non--last piece can reach is (p_{i+1}-1)), then a move by the first piece (if legal) or by the last piece decreases (T) by one, while a move on any piece (2 \le i \le n-1) leaves (T) unchanged (since for such a move the gap before the piece increases by one and the gap after the piece decreases by one).

It turns out that in an optimal play the outcome is decided by these (\textbf{decrement moves}) (i.e. moves that reduce (T)) in a way analogous to a simple subtraction game. In such a game the current player can force a win if and only if (T) is odd. Therefore, if (T) is odd the winning moves for the first player are exactly those legal moves that are decrement moves – that is, a legal move of piece (1) (if (p_1+1 < p_2) when (n \ge 2), or if (n=1) then just checking (p_1 < m)) and a legal move of the last piece (which is available if (p_n < m)). If (T) is even then no move is winning.

Your task is to output the number of winning moves available to the first player in the initial configuration.

\textbf{Input constraints and notes:}

• The first line of input contains two integers (m) and (n) where (m) is the cell number of the board's end, and (n) is the number of pieces.
• The second line contains (n) distinct increasing integers representing the positions (p_1, p_2, \dots, p_n) (none of which is equal to (m)).
• It is guaranteed that the number of test cases used to evaluate solutions has more than two examples.

\textbf{Note:} You may assume that the input is such that the described game always has at least one legal move.

inputFormat

The input consists of two lines:

• The first line contains two space‐separated integers: m (the highest cell number) and n (the number of pieces).
• The second line contains n space‐separated integers in increasing order representing the positions p1, p2, ..., pn. It is guaranteed that no piece is initially in cell m.

outputFormat

Output a single integer - the number of winning moves available to the first player.

Explanation: Compute \(T = m - p_1 - (n-1)\). If \(T\) is odd then the winning moves are exactly the legal decrement moves, namely:

• For n = 1: if p1 < m, the move is a winning move.
• For n > 1: if p1 + 1 < p2, the move of the first piece is a winning move; and if pn < m, the move of the last piece is a winning move.

If \(T\) is even, output 0.

sample

5 2
1 3

1