P15992 [PA 2026] 原题加强 2 / Wersja dla profesjonalistów 2

$\large{\bf{{警告：滥用本题评测，一次即可封号。}}}$

在 $2014$ 年，第八届初中生信息学奥林匹克决赛中出现了如下题目： > **跳房子** > > > Jasiu 喜欢和朋友们一起玩跳房子。他们一起决定对游戏规则稍作改进。一开始，在人行道上画出 $N$ 个正方形格子，依次排列。格子从左侧开始从 $1$ 起编号。某些格子上放有单个小石子。每位玩家选择一个起始格子，以及一个大于 $1$ 的整数 $K$。然后，从所选格子出发，每次跳 $K$ 个格子，直到跳过第 $N$ 号格子为止。玩家的得分等于其跳跃过程中落脚的有石子的格子数量。现在轮到 Jasiu 了，他非常想得到尽可能高的分数。已知石子的位置，请计算他能获得的最高分数。 > > > > #### 输入格式 > 标准输入的第一行是一个整数 $N$（$1 \le N \le 10^6$），表示格子的数量。第二行是一个长度为 $N$、由字符 `.` 和/或 `#` 组成的字符串。若第 $i$ 个字符为 `#`，则第 $i$ 个格子上有一颗石子，否则该格子为空。 > > > > #### 输出格式 > 标准输出的唯一一行应输出一个整数，表示 Jasiu 能获得的最高分数。 > > > > #### 样例 > > | 输入： | 输入： | 输入： | > |--------|--------|--------| > | $\texttt{8}\\\texttt{\#..\#...\#}$ | $\texttt{6}\\\texttt{\#\#\#\#..}$ |$\texttt{9}\\\texttt{\#.\#..\#..\#}$ | > | 输出： | 输出： | 输出： | > | `2` | `2` | `3` | $2014$ 年的初中生如今已是参加 PA 的专业选手，可以期待他们现在对难度显著更高的题目感兴趣。在本版本中，石子的布局并非一开始就固定不变——我们从一个有 $n$ 个格子的空棋盘开始，孩子们不断地添加和移除石子，每次操作后 Jasiu 都需要判断他能获得的最高分数。 **注意：** 网上也可以找到该题（原题）的题解，为方便起见我们也将其附于此处：`https://www.youtube.com/live/jxYu1MGGjBc`。但我们不保证其中的信息对解决我们这一版本的题目有任何帮助。

输入的第一行包含两个整数 $n$ 和 $q$（$1 \le n < 10\,000\,000$，$1 \le q < 1\,000\,000$）。 接下来 $q$ 行，每行描述一次事件。第 $i$ 次事件的描述为一个整数 $a_i$（$1 \le a_i \le n$），表示第 $i$ 次事件为：若第 $a_i$ 个格子上没有石子，则在该格子上放置一颗石子；若该格子上已有石子，则将其移除。

对于每次操作，输出一个整数：该操作后 Jasiu 能获得的最高分数。

### 样例解释 前三次操作后，棋盘状态与原题中第一个（最左侧）情形相同（精确地说，多出了第九个空格子，但不影响结果）。再经过三次操作后，得到第二个（中间）情形，最后得到第三个（右侧）情形。