English · Original
Chinese · Translation
Formal · Original
Recently, Dima met with Sasha in a philatelic store, and since then they are collecting coins together. Their favorite occupation is to sort collections of coins. Sasha likes having things in order, that is why he wants his coins to be arranged in a row in such a way that firstly come coins out of circulation, and then come coins still in circulation.
For arranging coins Dima uses the following algorithm. One step of his algorithm looks like the following:
1. He looks through all the coins from left to right;
2. If he sees that the _i_\-th coin is still in circulation, and (_i_ + 1)\-th coin is already out of circulation, he exchanges these two coins and continues watching coins from (_i_ + 1)\-th.
Dima repeats the procedure above until it happens that no two coins were exchanged during this procedure. Dima calls _hardness of ordering_ the number of steps required for him according to the algorithm above to sort the sequence, e.g. the number of times he looks through the coins from the very beginning. For example, for the ordered sequence hardness of ordering equals one.
Today Sasha invited Dima and proposed him a game. First he puts _n_ coins in a row, all of them are out of circulation. Then Sasha chooses one of the coins out of circulation and replaces it with a coin in circulation for _n_ times. During this process Sasha constantly asks Dima what is the hardness of ordering of the sequence.
The task is more complicated because Dima should not touch the coins and he should determine hardness of ordering in his mind. Help Dima with this task.
## Input
The first line contains single integer _n_ (1 ≤ _n_ ≤ 300 000) — number of coins that Sasha puts behind Dima.
Second line contains _n_ distinct integers _p_1, _p_2, ..., _p__n_ (1 ≤ _p__i_ ≤ _n_) — positions that Sasha puts coins in circulation to. At first Sasha replaces coin located at position _p_1, then coin located at position _p_2 and so on. Coins are numbered from left to right.
## Output
Print _n_ + 1 numbers _a_0, _a_1, ..., _a__n_, where _a_0 is a hardness of ordering at the beginning, _a_1 is a hardness of ordering after the first replacement and so on.
[samples]
## Note
Let's denote as _O_ coin out of circulation, and as _X_ — coin is circulation.
At the first sample, initially in row there are coins that are not in circulation, so Dima will look through them from left to right and won't make any exchanges.
After replacement of the first coin with a coin in circulation, Dima will exchange this coin with next three times and after that he will finally look through the coins and finish the process.
_XOOO_ → _OOOX_
After replacement of the third coin, Dima's actions look this way:
_XOXO_ → _OXOX_ → _OOXX_
After replacement of the fourth coin, Dima's actions look this way:
_XOXX_ → _OXXX_
Finally, after replacement of the second coin, row becomes consisting of coins that are in circulation and Dima will look through coins from left to right without any exchanges.
最近，Dima 在一家邮票店与 Sasha 相遇，从那时起他们就开始一起收集硬币。他们最喜爱的活动是整理硬币收藏。Sasha 喜欢有序的事物，因此他希望他的硬币排成一行，使得首先出现的是已退出流通的硬币，然后是仍在流通的硬币。
Dima 使用以下算法来排列硬币。该算法的每一步如下所示：
Dima 重复上述过程，直到在该过程中没有发生任何两枚硬币的交换为止。Dima 将 _排序难度_ 定义为根据上述算法对序列进行排序所需的步骤数，即他从头到尾查看硬币的次数。例如，对于已排序的序列，排序难度为 1。
今天，Sasha 邀请 Dima 玩一个游戏。首先，他在一行中放置 #cf_span[n] 枚硬币，所有硬币均为已退出流通状态。然后，Sasha 重复 #cf_span[n] 次以下操作：从已退出流通的硬币中选择一枚，并将其替换为一枚仍在流通的硬币。在此过程中，Sasha 不断询问 Dima 当前序列的排序难度。
这个任务更加复杂，因为 Dima 不能触碰硬币，他必须在脑海中确定排序难度。请帮助 Dima 完成这个任务。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300 000]) —— Sasha 放在 Dima 身后的硬币数量。
第二行包含 #cf_span[n] 个互不相同的整数 #cf_span[p1, p2, ..., pn] (#cf_span[1 ≤ pi ≤ n]) —— Sasha 将硬币替换为仍在流通状态的位置。Sasha 首先替换位置 #cf_span[p1] 的硬币，然后是位置 #cf_span[p2] 的硬币，依此类推。硬币从左到右编号。
请输出 #cf_span[n + 1] 个数字 #cf_span[a0, a1, ..., an]，其中 #cf_span[a0] 是初始状态的排序难度，#cf_span[a1] 是第一次替换后的排序难度，以此类推。
我们用 _O_ 表示已退出流通的硬币，用 _X_ 表示仍在流通的硬币。
在第一个样例中，初始时行中所有硬币均未流通，因此 Dima 从左到右查看一遍，不会进行任何交换。
在将第一枚硬币替换为仍在流通的硬币后，Dima 会将这枚硬币与右侧的硬币交换三次，然后再次从头查看硬币，完成整个过程。
_XOOO_ #cf_span[ → ] _OOOX_
在将第三枚硬币替换后，Dima 的操作如下：
_XOXO_ #cf_span[ → ] _OXOX_ #cf_span[ → ] _OOXX_
在将第四枚硬币替换后，Dima 的操作如下：
_XOXX_ #cf_span[ → ] _OXXX_
最后，在将第二枚硬币替换后，整行硬币均为仍在流通的状态，Dima 从左到右查看一遍，无需任何交换。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 300 000]) —— Sasha 放在 Dima 身后的硬币数量。第二行包含 #cf_span[n] 个互不相同的整数 #cf_span[p1, p2, ..., pn] (#cf_span[1 ≤ pi ≤ n]) —— Sasha 将硬币替换为仍在流通状态的位置。Sasha 首先替换位置 #cf_span[p1] 的硬币，然后是位置 #cf_span[p2] 的硬币，依此类推。硬币从左到右编号。
## Output
请输出 #cf_span[n + 1] 个数字 #cf_span[a0, a1, ..., an]，其中 #cf_span[a0] 是初始状态的排序难度，#cf_span[a1] 是第一次替换后的排序难度，以此类推。
[samples]
## Note
我们用 _O_ 表示已退出流通的硬币，用 _X_ 表示仍在流通的硬币。在第一个样例中，初始时行中所有硬币均未流通，因此 Dima 从左到右查看一遍，不会进行任何交换。在将第一枚硬币替换为仍在流通的硬币后，Dima 会将这枚硬币与右侧的硬币交换三次，然后再次从头查看硬币，完成整个过程。_XOOO_ #cf_span[ → ] _OOOX_。在将第三枚硬币替换后，Dima 的操作如下：_XOXO_ #cf_span[ → ] _OXOX_ #cf_span[ → ] _OOXX_。在将第四枚硬币替换后，Dima 的操作如下：_XOXX_ #cf_span[ → ] _OXXX_。最后，在将第二枚硬币替换后，整行硬币均为仍在流通的状态，Dima 从左到右查看一遍，无需任何交换。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of coins.
Let $ P = (p_1, p_2, \dots, p_n) $ be a sequence of distinct positions in $ \{1, 2, \dots, n\} $, representing the order in which coins are replaced from out-of-circulation (O) to in-circulation (X).
Let $ S_k \in \{O, X\}^n $ denote the state of the coin sequence after $ k $ replacements, for $ k = 0, 1, \dots, n $, where:
- Initially, $ S_0 = (O, O, \dots, O) $.
- For $ k \geq 1 $, $ S_k $ is obtained from $ S_{k-1} $ by replacing the coin at position $ p_k $ from O to X.
Let $ H(S) $ denote the *hardness of ordering* of a sequence $ S $, defined as the number of passes Dima makes from left to right until no adjacent pair $ (X, O) $ exists (i.e., all O’s are to the right of all X’s), where in each pass, every adjacent $ (X, O) $ is swapped to $ (O, X) $.
**Constraints**
1. $ 1 \leq n \leq 300{,}000 $
2. $ p_i \in \{1, 2, \dots, n\} $, all distinct.
**Objective**
Compute the sequence $ (a_0, a_1, \dots, a_n) $, where $ a_k = H(S_k) $ for $ k = 0, 1, \dots, n $.
API Response (JSON)
{
"problem": {
"name": "D. Sorting the Coins",
"description": {
"content": "Recently, Dima met with Sasha in a philatelic store, and since then they are collecting coins together. Their favorite occupation is to sort collections of coins. Sasha likes having things in order, t",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF876D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Recently, Dima met with Sasha in a philatelic store, and since then they are collecting coins together. Their favorite occupation is to sort collections of coins. Sasha likes having things in order, t...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "最近，Dima 在一家邮票店与 Sasha 相遇，从那时起他们就开始一起收集硬币。他们最喜爱的活动是整理硬币收藏。Sasha 喜欢有序的事物，因此他希望他的硬币排成一行，使得首先出现的是已退出流通的硬币，然后是仍在流通的硬币。\n\nDima 使用以下算法来排列硬币。该算法的每一步如下所示：\n\nDima 重复上述过程，直到在该过程中没有发生任何两枚硬币的交换为止。Dima 将 _排序难度_ 定义为根据...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of coins. \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a sequence of distinct positions in $ \\{1, 2, \\dots, n\\} $, representing the order in which...",
"is_translate": false,
"language": "Formal"
}
]
}