Hop-skip#4655
Country of Horses is played on a chessboard with dimensions 1 \times n, where the cells are numbered sequentially from to , left to right. Some of these cells contain horses, with at most one horse in each cell. The first horse is in cell a_1, the second in a_2, and the last in a_k, making a total of horses.
The King of Horses and his brother play a game on this board, alternating turns. The King of Horses moves first. On each turn, a player may select any horse on the board and move it to the nearest free cell to its right. A cell is considered free if it does not contain a horse. The player who first moves any horse to cell number wins the game.
Since the King of Horses moves first, he wants to know how many winning moves he has. In other words, how many moves he can make such that, no matter how the opponent plays, he can guarantee victory, assuming both play optimally.
The first line contains integers and (1 \leq n \leq 10^9, 1 \leq k \leq 10^6), the number of cells on the board and the number of horses.
The second line contains a strictly increasing sequence a_1, a_2, \ldots, a_k (1 \leq a_i < n, a_i < a_{i+1}), the positions of the horses.
It is guaranteed that no horse is in cell .
Print a single integer: the number of winning moves from the given position.
Example 1