最近,迪玛在一家集邮店遇见了萨莎,从那时起他们就一起收集硬币。他们最喜欢的工作是对硬币收藏品进行分类。萨沙喜欢把东西整理得井井有条,这就是为什么他希望他的硬币排成一排,先是不再流通的硬币,然后是仍在流通的硬币。
为了安排硬币,Dima 使用以下算法。他的算法的一个步骤如下所示:
1.他从左到右浏览所有硬币;
2. 如果他看到第 i 个硬币仍在流通,而第 (i + 1) 个硬币已经不再流通,则他交换这两个硬币并继续观看第 (i + 1) 个硬币。
Dima 重复上述过程,直到在此过程中没有交换两枚硬币。 Dima将他根据上面的算法对序列进行排序所需的步数称为排序难度,例如他从一开始就翻看硬币的次数。例如,对于有序序列,排序难度等于 1。
今天萨莎邀请了迪玛并提议他玩一场游戏。首先他把n枚硬币排成一排,所有硬币都不再流通了。然后萨莎选择其中一枚不再流通的硬币,并用流通了n次的硬币替换它。在这个过程中,萨莎不断地询问迪玛,序列排序的难度是什么。
任务更加复杂,因为迪马不应该碰硬币,他应该在心里确定排序的难度。帮助迪玛完成这项任务。
输入
第一行包含单个整数 n (1 ≤ n ≤ 300 000) — Sasha 在 Dima 后面放置的硬币数量。
第二行包含 n 个不同的整数 p1, p2, ..., pn (1 ≤ pi ≤ n) - Sasha 将硬币投入流通的位置。首先,Sasha 替换位置 p1 的硬币,然后替换位置 p2 的硬币,依此类推。硬币从左到右编号。
输出
打印n + 1个数字a0, a1, ..., an,其中a0是开始排序的硬度,a1是第一次替换后排序的硬度,依此类推。
示例
输入 #1
4 1 3 4 2
输出 #1
1 2 3 2 1
输入 #2
8 6 8 3 4 7 2 1 5
输出 #2
1 2 2 3 4 3 4 5 1
注意
我们用 O 表示已停止流通的硬币,用 X 表示流通中的硬币。
在第一个样本中,最初一行中有未流通的硬币,因此 Dima 将从左到右查看它们,并且不会进行任何交换。
在用流通的硬币替换第一枚硬币后,迪马将在接下来的3次兑换该硬币,之后他将最终检查硬币并完成该过程。
XOOO → OOOX
更换第三枚硬币后,迪玛的动作如下:
XOXO → OXOX → OOXX
更换第四枚硬币后,迪玛的动作如下:
XOXX → OXXX
最后,更换第二枚硬币后,该行将由正在流通的硬币组成,Dima 将从左到右查看硬币,而不进行任何交换。