Mirko 和 Slavko 开始学习踢踏舞。这种舞蹈主要包括用一种特殊的鞋子敲击地面。因为 Mirko 和 Slavko 学得很快，他们决定设计一套自己的编舞。

踢踏舞的编舞可以描述为一个由两个字母 L 和 R 组成的序列。L 表示你应该用左脚敲击地面，而 R 表示用右脚。Mirko 意识到，踢踏舞最令人兴奋的部分是那些不连续两次使用同一只脚的部分。他将编舞的价值定义为最长的连续子序列（子串）的长度，该子序列中不包含两个连续的 L 或连续的 R（即相邻字符互不相同）。

众所周知，设计一套编舞可能非常具有挑战性，在完成之前需要进行许多微小的修改。对于 Slavko 进行的每一次修改，他都想知道当前编舞的价值。一次修改是指将一个 L 变为 R，或者将一个 R 变为 L。

在进行任何修改之前，编舞仅由字母 L 组成。

输入格式

第一行包含两个整数，编舞的长度 $N$（$1 \le N \le 200\,000$）和修改的次数 $Q$（$1 \le Q \le 200\,000$）。

接下来的 $Q$ 行，每行包含一个整数，表示 Mirko 和 Slavko 修改的位置（按修改顺序给出，位置下标从 $1$ 开始）。

输出格式

输出必须包含 $Q$ 个整数，每行一个，表示每次修改后编舞的当前价值。

样例

输入格式 1

6 2
2
4

输出格式 1

3
5

输入格式 2

6 5
4
1
1
2
6

输出格式 2

3
3
3
5
6

说明

对于第一个样例的解释：编舞的变化过程为：LLLLLL $\to$ LRLLLL $\to$ LRLRLL。