问题描述

有N个格子按从左到右的顺序排成一行。最初，所有格子都被涂成白色。

需要依次处理Q个查询。第i个查询会给出一个1到N之间的整数Aᵢ，并执行以下操作：

将从左数第Aᵢ个格子的颜色翻转。具体来说，如果从左数第Aᵢ个格子是白色，就将其涂成黑色；如果是黑色，就将其涂成白色。

然后，求出连续黑色格子区间的数量。

这里，连续黑色格子区间指的是满足以下所有条件的整数对(l, r)（1≤l≤r≤N）：

• 从左数第l、l+1、…、r个格子全部被涂成黑色。
• 要么l=1，要么从左数第(l-1)个格子是白色。
• 要么r=N，要么从左数第(r+1)个格子是白色。

约束条件

• 1≤N, Q≤5×10⁵
• 1≤Aᵢ≤N
• 输入均为整数

输入格式

输入通过标准输入按以下格式给出：

N Q
A₁ A₂ … A_Q

输出格式

输出Q行。第i行（1≤i≤Q）输出第i个查询的答案。

输入示例1

5 7
2 3 3 5 1 5 2

输出示例1

1
1
1
2
2
1
1

输入示例1解释

以下将从左数第i个格子称为格子i。

每个查询后的状态如下：

• 第1个查询后，只有格子2是黑色。连续黑色格子区间有1个：(l, r)=(2, 2)。
• 第2个查询后，格子2、3是黑色。连续黑色格子区间有1个：(l, r)=(2, 3)。
• 第3个查询后，只有格子2是黑色。连续黑色格子区间有1个：(l, r)=(2, 2)。
• 第4个查询后，格子2、5是黑色。连续黑色格子区间有2个：(l, r)=(2, 2)、(5, 5)。
• 第5个查询后，格子1、2、5是黑色。连续黑色格子区间有2个：(l, r)=(1, 2)、(5, 5)。
• 第6个查询后，只有格子1、2是黑色。连续黑色格子区间有1个：(l, r)=(1, 2)。
• 第7个查询后，只有格子1是黑色。连续黑色格子区间有1个：(l, r)=(1, 1)。

因此，按顺序输出1、1、1、2、2、1、1。

输入示例2

1 2
1 1

输出示例2

1
0

输入示例2解释

• 第1个查询后，格子1是黑色。连续黑色格子区间有1个：(l, r)=(1, 1)。
• 第2个查询后，所有格子都是白色。因此，第2行输出0。

输入示例3

3 3
1 3 2

输出示例3

1
2
1