English · Original
Chinese · Translation
Formal · Original
You are given an array of positive integers. While there are at least two equal elements, we will perform the following operation. We choose the smallest value $x$ that occurs in the array $2$ or more times. Take the first two occurrences of $x$ in this array (the two leftmost occurrences). Remove the left of these two occurrences, and the right one is replaced by the sum of this two values (that is, $2 \cdot x$).
Determine how the array will look after described operations are performed.
For example, consider the given array looks like $[3, 4, 1, 2, 2, 1, 1]$. It will be changed in the following way: $[3, 4, 1, 2, 2, 1, 1]~\rightarrow~[3, 4, 2, 2, 2, 1]~\rightarrow~[3, 4, 4, 2, 1]~\rightarrow~[3, 8, 2, 1]$.
If the given array is look like $[1, 1, 3, 1, 1]$ it will be changed in the following way: $[1, 1, 3, 1, 1]~\rightarrow~[2, 3, 1, 1]~\rightarrow~[2, 3, 2]~\rightarrow~[3, 4]$.
## Input
The first line contains a single integer $n$ ($2 \le n \le 150\,000$) — the number of elements in the array.
The second line contains a sequence from $n$ elements $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{9}$) — the elements of the array.
## Output
In the first line print an integer $k$ — the number of elements in the array after all the performed operations. In the second line print $k$ integers — the elements of the array after all the performed operations.
[samples]
## Note
The first two examples were considered in the statement.
In the third example all integers in the given array are distinct, so it will not change.
你被给定一个正整数数组。只要数组中存在至少两个相等的元素，我们就执行以下操作：选择在数组中出现至少两次的最小值 $x$。取出该值的前两次出现（最左边的两个）。移除左边的那个，将右边的那个替换为这两个值的和（即 $2 \cdot x$）。
请确定在执行上述操作后，数组会变成什么样子。
例如，考虑数组 $[ 3, 4, 1, 2, 2, 1, 1 ]$，它将按如下方式变化：$[ 3, 4, 1, 2, 2, 1, 1 ] \rightarrow [ 3, 4, 2, 2, 2, 1 ] \rightarrow [ 3, 4, 4, 2, 1 ] \rightarrow [ 3, 8, 2, 1 ]$。
如果给定数组为 $[ 1, 1, 3, 1, 1 ]$，它将按如下方式变化：$[ 1, 1, 3, 1, 1 ] \rightarrow [ 2, 3, 1, 1 ] \rightarrow [ 2, 3, 2 ] \rightarrow [ 3, 4 ]$。
第一行包含一个整数 $n$（$2 \leq n \leq 150\,000$）——数组中元素的个数。
第二行包含一个由 $n$ 个元素组成的序列 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）——数组的元素。
第一行输出一个整数 $k$ —— 所有操作完成后数组中元素的个数。第二行输出 $k$ 个整数 —— 所有操作完成后数组的元素。
题面中已讨论了前两个例子。
在第三个例子中，给定数组中的所有整数互不相同，因此数组不会改变。
## Input
第一行包含一个整数 $n$（$2 \leq n \leq 150\,000$）——数组中元素的个数。第二行包含一个由 $n$ 个元素组成的序列 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）——数组的元素。
## Output
第一行输出一个整数 $k$ —— 所有操作完成后数组中元素的个数。第二行输出 $k$ 个整数 —— 所有操作完成后数组的元素。
[samples]
## Note
前两个例子已在题面中讨论。在第三个例子中，给定数组中的所有整数互不相同，因此数组不会改变。
**Definitions**
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, with $ n \geq 2 $.
**Operation**
While there exists a value $ x $ that appears at least twice in $ A $:
- Let $ x = \min \{ y \in A \mid \text{freq}_A(y) \geq 2 \} $.
- Let $ i < j $ be the indices of the two leftmost occurrences of $ x $ in $ A $.
- Remove $ a_i $, and replace $ a_j $ with $ 2x $.
- The resulting sequence is $ A $ with the $ i $-th element deleted and the $ j $-th element updated to $ 2x $.
**Constraints**
1. $ 2 \leq n \leq 150{,}000 $
2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Compute the final state of the array $ A $ after no further operations can be performed (i.e., all elements are distinct). Output:
- $ k $: the number of elements in the final array.
- The final sequence of $ k $ distinct positive integers.
API Response (JSON)
{
"problem": {
"name": "D. Merge Equals",
"description": {
"content": "You are given an array of positive integers. While there are at least two equal elements, we will perform the following operation. We choose the smallest value $x$ that occurs in the array $2$ or more",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF962D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given an array of positive integers. While there are at least two equal elements, we will perform the following operation. We choose the smallest value $x$ that occurs in the array $2$ or more...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "你被给定一个正整数数组。只要数组中存在至少两个相等的元素，我们就执行以下操作：选择在数组中出现至少两次的最小值 $x$。取出该值的前两次出现（最左边的两个）。移除左边的那个，将右边的那个替换为这两个值的和（即 $2 \\cdot x$）。\n\n请确定在执行上述操作后，数组会变成什么样子。\n\n例如，考虑数组 $[ 3, 4, 1, 2, 2, 1, 1 ]$，它将按如下方式变化：$[ 3, 4, 1, ...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, with $ n \\geq 2 $.\n\n**Operation** \nWhile there exists a value $ x $ that appears at least twice in $ A $: \n- ...",
"is_translate": false,
"language": "Formal"
}
]
}