CF875B Sorting the Coins

最近，Dima 在一家集邮店遇见了 Sasha，从那以后他们便一起收集硬币。他们最喜欢做的事就是整理硬币收藏。Sasha 喜欢井然有序的东西，因此他希望自己的硬币排成一排时，先是所有已经退出流通的硬币，再是所有仍在流通中的硬币。 为此，Dima 使用以下算法进行整理。他的每一步操作如下： 1. 他从左到右遍历所有硬币； 2. 如果发现第 $i$ 枚硬币仍在流通，而第 $(i+1)$ 枚硬币已经退出流通，他就交换这两枚硬币，然后从第 $(i+1)$ 枚硬币继续观察后面的硬币。 Dima 重复上述过程，直到在一次遍历中没有发生任何交换为止。Dima 将对序列进行排序所需的遍历次数称为“排序难度”，即他从头到尾遍历硬币的次数。例如，如果一开始序列已排好序，则排序难度为 $1$。 今天 Sasha 邀请 Dima 玩一个游戏。首先，Sasha 依次摆放 $n$ 枚已经退出流通的硬币成一排。接着，Sasha 每次从中选择一枚已经退出流通的硬币，换成一枚仍在流通的硬币，这一过程连续进行 $n$ 次。在这期间，Sasha 不断询问 Dima 当前序列的排序难度。 难点在于，Dima 不能实际触碰硬币，只能在脑中判断排序难度。请帮助 Dima 完成这个任务。

第一行包含一个整数 $n$（$1 \leq n \leq 300000$），表示 Sasha 摆放在 Dima 面前的硬币数量。 第二行包含 $n$ 个不同的整数 $p_{1}, p_{2}, ..., p_{n}$（$1 \leq p_{i} \leq n$），表示 Sasha 每次把第 $p_{i}$ 个位置的硬币替换为仍在流通的硬币。硬币的位置编号从左到右依次为 $1$ 到 $n$。

输出 $n+1$ 个整数 $a_{0}, a_{1}, ..., a_{n}$，其中 $a_{0}$ 表示初始状态下的排序难度，$a_{1}$ 表示第一次替换后的排序难度，依此类推。

我们用 O 表示已经退出流通的硬币，X 表示仍在流通的硬币。 在第一个样例中，最初所有硬币都是 O，因此 Dima 从左到右遍历一遍，没有需要交换的硬币。 第一次替换后，Dima 将第一枚硬币换成 X，随后该 X 会向右连续移动三次，最终状态： XOOO $ \to $ OOOX 替换第三枚硬币后，Dima 的操作如下： XOXO $ \to $ OXOX $ \to $ OOXX 替换第四枚硬币后： XOXX $ \to $ OXXX 最后，替换第二枚硬币后，所有硬币都是 X，Dima 只需遍历一次，不再有交换。 由 ChatGPT 5 翻译