[AdditionalFile5690.zip](file://AdditionalFile5690.zip?type=additional_file)

#5690. 「PA 2026」Wersja dla profesjonalistów 2

标签: 传统 | 时间限制: 10000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 5 Wersja dla profesjonalistów 2

在 2014 年的第八届初中信息学奥林匹克竞赛决赛中，出现了以下题目：

小雅喜欢和朋友玩跳房子游戏。他们决定稍微改进一下规则。起初，人行道上画有 $N$ 个方形格子，并排排列。格子从 $1$ 开始编号（从左侧开始）。有些格子里有单独的鹅卵石。每位玩家选择一个起始格子以及一个大于 $1$ 的整数 $K$。然后，从选定的格子开始，每次跳 $K$ 个格子，直到跳出第 $N$ 个格子。玩家的得分等于跳跃过程中落到的带有鹅卵石的格子数量。现在轮到小雅了，他非常想获得最高分。已知鹅卵石的位置，计算他能获得的最大分数。

2014 年的初中生如今已是算法竞赛的选手，我们期待他们挑战难度明显更高的题目。在本题的加强版中，鹅卵石的布局不再是固定不变的。我们从一个空的 $n$ 个格子的路面开始，孩子们在玩耍过程中不断添加和移走鹅卵石。每次变动后，小雅都想知道他能获得的最高分数是多少。

注意：互联网上可以找到该题目的解析（链接略）。然而，我们不保证其中包含的信息对解决本题有任何帮助。

输入格式

第一行输入包含两个整数 $n$ 和 $q$ $(1 \leq n \leq 10000000, 1 \leq q \leq 1000000)$，分别表示人行道上的格子数量以及需要考虑的事件数量。

接下来的 $q$ 行描述了事件；第 $i$ 行包含一个整数 $a_{i}$ $(1 \leq a_{i} \leq n)$，表示第 $i$ 个事件是在第 $a_{i}$ 个格子里添加一颗鹅卵石（如果该格子原本没有鹅卵石）或者移走第 $a_{i}$ 个格子的鹅卵石（如果原本有鹅卵石）。

输出格式

输出 $q$ 行；第 $i$ 行应包含一个整数，表示第 $i$ 个事件发生后小雅能获得的最高分数。

样例

输入

9 10
1
4
8
2
3
8
6
9
2
4

输出

1
2
2
3
3
2
3
3
3
3

在前三次事件后，我们得到了原始题目中的第一种情况（假设有一个额外的、空的第九个格子，它不影响分数）。再经过三次事件后，得到第二种（中间）情况，最后得到第三种（右侧）情况。