问题描述

有 N 个方块从左到右排成一行。初始时，所有方块都被涂成白色。

依次处理 Q 个查询。第 i 个查询给出一个整数 Ai（1 ≤ Ai ≤ N），并执行以下操作：翻转从左数第 Ai 个方块的颜色。具体来说，如果第 Ai 个方块是白色，则将其涂黑；如果是黑色，则将其涂白。

然后，计算连续黑色方块区间的数量。

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

1. 从左数第 l 个、第 (l+1) 个、...、第 r 个方块都是黑色；
2. 要么 l = 1，要么第 (l-1) 个方块是白色；
3. 要么 r = N，要么第 (r+1) 个方块是白色。

约束条件

• 1 ≤ N, Q ≤ 5 × 10^5
• 1 ≤ Ai ≤ N
• 所有输入值均为整数。

输入

输入通过标准输入给出，格式如下：

N Q
A1 A2 ... AQ

输出

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

样例输入 1

5 7
2 3 3 5 1 5 2

样例输出 1

1
1
1
2
2
1
1

解释：

从左数第 i 个方块称为方块 i。每个查询后的状态如下：

1. 第 1 次查询后，只有方块 2 是黑色。有 1 个连续黑色区间：(2,2)。
2. 第 2 次查询后，方块 2 和 3 是黑色。有 1 个连续黑色区间：(2,3)。
3. 第 3 次查询后，只有方块 2 是黑色。有 1 个连续黑色区间：(2,2)。
4. 第 4 次查询后，方块 2 和 5 是黑色。有 2 个连续黑色区间：(2,2) 和 (5,5)。
5. 第 5 次查询后，方块 1、2 和 5 是黑色。有 2 个连续黑色区间：(1,2) 和 (5,5)。
6. 第 6 次查询后，只有方块 1 和 2 是黑色。有 1 个连续黑色区间：(1,2)。
7. 第 7 次查询后，只有方块 1 是黑色。有 1 个连续黑色区间：(1,1)。

因此，输出为 1,1,1,2,2,1,1，每行一个数字。

样例输入 2

1 2
1 1

样例输出 2

1
0

解释：

1. 第 1 次查询后，方块 1 是黑色。有 1 个连续黑色区间：(1,1)。
2. 第 2 次查询后，所有方块都是白色。因此第 2 行输出 0。

样例输入 3

3 3
1 3 2

样例输出 3

1
2
1

解释：

1. 第 1 次查询后，方块 1 是黑色。有 1 个连续黑色区间：(1,1)。
2. 第 2 次查询后，方块 1 和 3 是黑色。有 2 个连续黑色区间：(1,1) 和 (3,3)。
3. 第 3 次查询后，方块 1 和 2 是黑色。有 1 个连续黑色区间：(1,2)。