1382. Game

单点时限: 5.0 sec

内存限制: 256 MB

Let us consider a game on a rectangular board m x 1 consisting of m elementary squares numbered successively from 1 to m. There are n pawns on the board, each on a distinct square. None of them occupies the square with number m. Each single move in the is the following action: the moving player picks a pawn from any occupied square chosen at will and places it on the first unoccupied square with a larger number. The two players make moves in turn. The one who puts a pawn on the last square, i.e. the square with a number m, wins.

In the case presented in the figure (m = 7), a player is allowed to move a pawn from square no. 2 to 4, from square no. 3 to 4 or from square no. 6 to 7. The latter ends the game.

We say a player’s move is winning if after making it he can win the game, no matter what moves his opponent makes.

Task

Write a programme that:

reads the size of a board and the initial setup of pawns from the standard input,

determines the number of distinct winning moves the starting player may choose in the given initial situation,

writes the result to the standard output.

输入格式

The first line of the input contains two integers m and n (2 <= m <= 10^9, 1 <= n <= 10^6, n < m) separated by a single space. The second line contains n increasing numbers - these are the numbers of squares the pawns are set on. Numbers in the line are separated by single spaces.

输出格式

The first and only output line should contain the number of distinct winning moves possible for the starting player in the given initial situation.

样例

Input
5 2
1 3
hint:
5 2
2 3
Output
1
hint:
0

6 人解决,12 人已尝试。

11 份提交通过,共有 54 份提交。

7.7 EMB 奖励。

创建: 12 年,6 月前.

修改: 2 年,5 月前.

最后提交: 10 月前.

来源: POI

题目标签