{"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 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$).\n\nDetermine how the array will look after described operations are performed.\n\nFor 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]$.\n\nIf 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]$.\n\n## Input\n\nThe first line contains a single integer $n$ ($2 \\le n \\le 150\\,000$) — the number of elements in the array.\n\nThe 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.\n\n## Output\n\nIn 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.\n\n[samples]\n\n## Note\n\nThe first two examples were considered in the statement.\n\nIn the third example all integers in the given array are distinct, so it will not change.","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, 2, 2, 1, 1 ] \\rightarrow [ 3, 4, 2, 2, 2, 1 ] \\rightarrow [ 3, 4, 4, 2, 1 ] \\rightarrow [ 3, 8, 2, 1 ]$。\n\n如果给定数组为 $[ 1, 1, 3, 1, 1 ]$，它将按如下方式变化：$[ 1, 1, 3, 1, 1 ] \\rightarrow [ 2, 3, 1, 1 ] \\rightarrow [ 2, 3, 2 ] \\rightarrow [ 3, 4 ]$。\n\n第一行包含一个整数 $n$（$2 \\leq n \\leq 150\\,000$）——数组中元素的个数。\n\n第二行包含一个由 $n$ 个元素组成的序列 $a_1, a_2, \\dots, a_n$（$1 \\leq a_i \\leq 10^9$）——数组的元素。\n\n第一行输出一个整数 $k$ —— 所有操作完成后数组中元素的个数。第二行输出 $k$ 个整数 —— 所有操作完成后数组的元素。\n\n题面中已讨论了前两个例子。\n\n在第三个例子中，给定数组中的所有整数互不相同，因此数组不会改变。\n\n## Input\n\n第一行包含一个整数 $n$（$2 \\leq n \\leq 150\\,000$）——数组中元素的个数。第二行包含一个由 $n$ 个元素组成的序列 $a_1, a_2, \\dots, a_n$（$1 \\leq a_i \\leq 10^9$）——数组的元素。\n\n## Output\n\n第一行输出一个整数 $k$ —— 所有操作完成后数组中元素的个数。第二行输出 $k$ 个整数 —— 所有操作完成后数组的元素。\n\n[samples]\n\n## Note\n\n前两个例子已在题面中讨论。在第三个例子中，给定数组中的所有整数互不相同，因此数组不会改变。","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- Let $ x = \\min \\{ y \\in A \\mid \\text{freq}_A(y) \\geq 2 \\} $.  \n- Let $ i < j $ be the indices of the two leftmost occurrences of $ x $ in $ A $.  \n- Remove $ a_i $, and replace $ a_j $ with $ 2x $.  \n- The resulting sequence is $ A $ with the $ i $-th element deleted and the $ j $-th element updated to $ 2x $.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 150{,}000 $  \n2. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCompute the final state of the array $ A $ after no further operations can be performed (i.e., all elements are distinct). Output:  \n- $ k $: the number of elements in the final array.  \n- The final sequence of $ k $ distinct positive integers.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF962D","tags":["data structures","implementation"],"sample_group":[["7\n3 4 1 2 2 1 1","4\n3 8 2 1"],["5\n1 1 3 1 1","2\n3 4"],["5\n10 40 20 50 30","5\n10 40 20 50 30"]],"created_at":"2026-03-03 11:00:39"}}