关键观察

把每个“不可用座位”视作一个分隔点，连续可用段就是相邻分隔点之间的空隙。 若一段长度为 $L$，可坐人数为 $\left\lceil \tfrac{L}{2}\right\rceil$ = $\left\lfloor \tfrac{L+1}{2}\right\rfloor$。

因此答案始终是所有空隙的

题目内容

教室里有一排 $n$ 把椅子，从 $1$ 到 $n$ 编号，每把椅子可以容纳一个人。但是由于在教室里禁止贴贴，相邻的两把椅子上不能同时有人坐。一开始，所有的椅子都是可用的。接下来，有 $q$ 个事件会依次发生:

• 在第 $1$ 个事件中，给定一个椅子编号 $k$ 。如果编号为 $k$ 的椅子是可用的，则将它置为不可用;否则将它置为可用。注意,每次事件的修改都是永久的 .

• 你需要输出 $q$ 个整数:第 $i$ 个整数代表在第 $i$ 个事件后，教室的椅子最多能容纳多少人.

输入描述

第一行包含两个整数 $n,q(1≦n≦10^9,1≦q≦2·10^5)$,表示椅子的数量和事件的数量。

接下来 $q$ 行，第 $i$ 行包含一个整数 $k_i(1≦k_i≦n)$,表示第 $i$ 个事件中的椅子编号。

输出描述

输出 $q$ 行，每行包含一个整数，其中第 $i$ 行的整数代表第 $i$ 次事件后的教室椅子的最大容纳人数。

样例1

输入

5 3
1
2
1

输出

2
2
3

说明 我们用 $1$ 表示椅子可用，$0$ 表示椅子不可用。

• 在第 $1$ 次事件后，$1$ 号椅子变为不可用，椅子的状态为 $01111$ .最多容纳 $2$ 个人。一个可行的方案为:第一个人坐在 $2$ 号椅子，第二个人坐在 $4$ 号椅子。

• 在第 $2$ 次事件后，$2$ 号椅子变为不可用，椅子的状态为 $00111$ .最多容纳 $2$ 个人。一个可行的方案为:第一个人坐在 $3$ 号椅子，第二个人坐在 $5$ 号椅子。

• 在第 $3$ 次事件后，$1$ 号椅子变为可用，椅子的状态为 $10111$ ，最多容纳 $3$ 个人。一个可行的方案为:第一个人坐在 $1$ 号椅子，第二个人坐在 $3$ 号椅子，第三个人坐在 $5$ 号椅子。

样例2

输入

1000000 3
1
1000000
99999

输出

500000
499999
499999