English · Original
Chinese · Translation
Formal · Original
You are given a sequence of positive integers _a_1, _a_2, ..., _a__n_.
While possible, you perform the following operation: find a pair of equal consecutive elements. If there are more than one such pair, find the leftmost (with the smallest indices of elements). If the two integers are equal to _x_, delete both and insert a single integer _x_ + 1 on their place. This way the number of elements in the sequence is decreased by 1 on each step.
You stop performing the operation when there is no pair of equal consecutive elements.
For example, if the initial sequence is \[5, 2, 1, 1, 2, 2\], then after the first operation you get \[5, 2, 2, 2, 2\], after the second — \[5, 3, 2, 2\], after the third — \[5, 3, 3\], and finally after the fourth you get \[5, 4\]. After that there are no equal consecutive elements left in the sequence, so you stop the process.
Determine the final sequence after you stop performing the operation.
## Input
The first line contains a single integer _n_ (2 ≤ _n_ ≤ 2·105) — the number of elements in the sequence.
The second line contains the sequence of integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109).
## Output
In the first line print a single integer _k_ — the number of elements in the sequence after you stop performing the operation.
In the second line print _k_ integers — the sequence after you stop performing the operation.
[samples]
## Note
The first example is described in the statements.
In the second example the initial sequence is \[1000000000, 1000000000, 1000000000, 1000000000\]. After the first operation the sequence is equal to \[1000000001, 1000000000, 1000000000\]. After the second operation the sequence is \[1000000001, 1000000001\]. After the third operation the sequence is \[1000000002\].
In the third example there are no two equal consecutive elements initially, so the sequence does not change.
你被给定一个正整数序列 #cf_span[a1, a2, ..., an]。
在可能的情况下，你执行以下操作：找到一对相等的相邻元素。如果有多个这样的配对，选择最左边的（即元素下标最小的）。如果这两个整数都等于 #cf_span[x]，则将它们删除，并在它们的位置插入一个整数 #cf_span[x + 1]。这样，序列的元素个数在每一步减少 #cf_span[1]。
当序列中不再存在任何相等的相邻元素时，你停止操作。
例如，如果初始序列为 #cf_span[[5, 2, 1, 1, 2, 2]]，则第一次操作后得到 #cf_span[[5, 2, 2, 2, 2]]，第二次操作后得到 #cf_span[[5, 3, 2, 2]]，第三次操作后得到 #cf_span[[5, 3, 3]]，第四次操作后得到 #cf_span[[5, 4]]。此时序列中已无相等的相邻元素，因此停止过程。
请确定在停止操作后得到的最终序列。
第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2·105]) —— 序列中元素的个数。
第二行包含整数序列 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109])。
第一行输出一个整数 #cf_span[k] —— 停止操作后序列中元素的个数。
第二行输出 #cf_span[k] 个整数 —— 停止操作后的序列。
第一个例子已在题面中描述。
在第二个例子中，初始序列为 #cf_span[[1000000000, 1000000000, 1000000000, 1000000000]]。第一次操作后序列变为 #cf_span[[1000000001, 1000000000, 1000000000]]。第二次操作后序列变为 #cf_span[[1000000001, 1000000001]]。第三次操作后序列变为 #cf_span[[1000000002]]。
在第三个例子中，初始序列中没有相等的相邻元素，因此序列保持不变。
## Input
第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 2·105]) —— 序列中元素的个数。第二行包含整数序列 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109])。
## Output
第一行输出一个整数 #cf_span[k] —— 停止操作后序列中元素的个数。第二行输出 #cf_span[k] 个整数 —— 停止操作后的序列。
[samples]
## Note
第一个例子已在题面中描述。在第二个例子中，初始序列为 #cf_span[[1000000000, 1000000000, 1000000000, 1000000000]]。第一次操作后序列变为 #cf_span[[1000000001, 1000000000, 1000000000]]。第二次操作后序列变为 #cf_span[[1000000001, 1000000001]]。第三次操作后序列变为 #cf_span[[1000000002]]。在第三个例子中，初始序列中没有相等的相邻元素，因此序列保持不变。
**Definitions**
Let $ n \in \mathbb{Z} $ be the initial length of the sequence.
Let $ A = (a_1, a_2, \dots, a_n) $ be the initial sequence of positive integers.
**Operation**
While there exists an index $ i \in \{1, \dots, |A|-1\} $ such that $ a_i = a_{i+1} $:
- Let $ i $ be the smallest such index.
- Replace the subsequence $ (a_i, a_{i+1}) $ with $ (a_i + 1) $, reducing the sequence length by 1.
**Constraints**
1. $ 2 \leq n \leq 2 \cdot 10^5 $
2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Compute the final sequence $ A' $ obtained after no consecutive equal elements remain.
Output:
- $ k = |A'| $, the length of the final sequence.
- The sequence $ A' = (a'_1, a'_2, \dots, a'_k) $.
API Response (JSON)
{
"problem": {
"name": "E. Merge Equal Elements",
"description": {
"content": "You are given a sequence of positive integers _a_1, _a_2, ..., _a__n_. While possible, you perform the following operation: find a pair of equal consecutive elements. If there are more than one such ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF953E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given a sequence of positive integers _a_1, _a_2, ..., _a__n_.\n\nWhile possible, you perform the following operation: find a pair of equal consecutive elements. If there are more than one such ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个正整数序列 #cf_span[a1, a2, ..., an]。\n\n在可能的情况下，你执行以下操作：找到一对相等的相邻元素。如果有多个这样的配对，选择最左边的（即元素下标最小的）。如果这两个整数都等于 #cf_span[x]，则将它们删除，并在它们的位置插入一个整数 #cf_span[x + 1]。这样，序列的元素个数在每一步减少 #cf_span[1]。\n\n当序列中不再存在任何相等的...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the initial length of the sequence. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the initial sequence of positive integers.\n\n**Operation** \nWhile there exists...",
"is_translate": false,
"language": "Formal"
}
]
}