关键观察

把每个“不可用座位”视作一个分隔点，连续可用段就是相邻分隔点之间的空隙。 若一段长度为 $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)$,表示椅子的数量和事件的数量。