Winning Moves in a Pawn Game

Consider a game played on a 1 by m rectangular board. The cells are numbered from 1 to m. There are n pawns on distinct cells, and cell m is empty.

Two players alternate turns. On a turn, the player chooses a pawn on cell i and must move it to cell j, where j is the smallest-numbered empty cell greater than i. In other words, the pawn moves to the first empty cell to its right.

The player who moves a pawn into cell m wins immediately. For the current board position, count how many legal moves are winning moves. A move is winning if, after making that move, the current player can force a win no matter how the opponent responds.

The first line contains two positive integers m and n.

• 2 <= m <= 10^9
• 1 <= n <= 10^6
• n < m

The second line contains n positive integers in increasing order. These are the cells currently occupied by pawns. Cell m is empty.

Print the number of winning moves available to the player whose turn it is.