{"problem":{"name":"D. Make a Permutation!","description":{"content":"Ivan has an array consisting of _n_ elements. Each of the elements is an integer from 1 to _n_. Recently Ivan learned about permutations and their lexicographical order. Now he wants to change (repla","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF864D"},"statements":[{"statement_type":"Markdown","content":"Ivan has an array consisting of _n_ elements. Each of the elements is an integer from 1 to _n_.\n\nRecently Ivan learned about permutations and their lexicographical order. Now he wants to change (replace) _minimum_ number of elements in his array in such a way that his array becomes a _permutation_ (i.e. each of the integers from 1 to _n_ was encountered in his array exactly once). If there are multiple ways to do it he wants to find the _lexicographically minimal_ permutation among them.\n\nThus minimizing the number of changes has the first priority, lexicographical minimizing has the second priority.\n\nIn order to determine which of the two permutations is lexicographically smaller, we compare their first elements. If they are equal — compare the second, and so on. If we have two permutations _x_ and _y_, then _x_ is lexicographically smaller if _x__i_ < _y__i_, where _i_ is the first index in which the permutations _x_ and _y_ differ.\n\nDetermine the array Ivan will obtain after performing all the changes.\n\n## Input\n\nThe first line contains an single integer _n_ (2 ≤ _n_ ≤ 200 000) — the number of elements in Ivan's array.\n\nThe second line contains a sequence of integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ _n_) — the description of Ivan's array.\n\n## Output\n\nIn the first line print _q_ — the minimum number of elements that need to be changed in Ivan's array in order to make his array a permutation. In the second line, print the _lexicographically minimal_ permutation which can be obtained from array with _q_ changes.\n\n[samples]\n\n## Note\n\nIn the first example Ivan needs to replace number three in position 1 with number one, and number two in position 3 with number four. Then he will get a permutation _\\[1, 2, 4, 3\\]_ with only two changed numbers — this permutation is lexicographically minimal among all suitable.\n\nIn the second example Ivan does not need to change anything because his array already is a permutation.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Ivan has an array consisting of $n$ elements. Each of the elements is an integer from $1$ to $n$.\n\nRecently Ivan learned about permutations and their lexicographical order. Now he wants to change (replace) _minimum_ number of elements in his array in such a way that his array becomes a _permutation_ (i.e. each of the integers from $1$ to $n$ was encountered in his array exactly once). If there are multiple ways to do it he wants to find the _lexicographically minimal_ permutation among them.\n\nThus minimizing the number of changes has the first priority, lexicographical minimizing has the second priority.\n\nIn order to determine which of the two permutations is lexicographically smaller, we compare their first elements. If they are equal — compare the second, and so on. If we have two permutations $x$ and $y$, then $x$ is lexicographically smaller if $x_i < y_i$, where $i$ is the first index in which the permutations $x$ and $y$ differ.\n\nDetermine the array Ivan will obtain after performing all the changes.\n\nThe first line contains an single integer $n$ ($2 ≤ n ≤ 200 000$) — the number of elements in Ivan's array.\n\nThe second line contains a sequence of integers $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ n$) — the description of Ivan's array.\n\nIn the first line print $q$ — the minimum number of elements that need to be changed in Ivan's array in order to make his array a permutation. In the second line, print the _lexicographically minimal_ permutation which can be obtained from array with $q$ changes.\n\nIn the first example Ivan needs to replace number three in position $1$ with number one, and number two in position $3$ with number four. Then he will get a permutation $[1, 2, 4, 3]$ with only two changed numbers — this permutation is lexicographically minimal among all suitable. \n\nIn the second example Ivan does not need to change anything because his array already is a permutation.\n\n## Input\n\nThe first line contains an single integer $n$ ($2 ≤ n ≤ 200 000$) — the number of elements in Ivan's array.The second line contains a sequence of integers $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ n$) — the description of Ivan's array.\n\n## Output\n\nIn the first line print $q$ — the minimum number of elements that need to be changed in Ivan's array in order to make his array a permutation. In the second line, print the _lexicographically minimal_ permutation which can be obtained from array with $q$ changes.\n\n[samples]\n\n## Note\n\nIn the first example Ivan needs to replace number three in position $1$ with number one, and number two in position $3$ with number four. Then he will get a permutation $[1, 2, 4, 3]$ with only two changed numbers — this permutation is lexicographically minimal among all suitable. In the second example Ivan does not need to change anything because his array already is a permutation.","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ 2 \\leq n \\leq 200{,}000 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers where $ 1 \\leq a_i \\leq n $ for all $ i $.  \n\nLet $ S = \\{1, 2, \\dots, n\\} $ be the set of required values for a permutation.  \nLet $ F \\subseteq S $ be the set of *missing* values: $ F = S \\setminus \\{a_i \\mid 1 \\leq i \\leq n\\} $.  \nLet $ D \\subseteq \\{1, 2, \\dots, n\\} $ be the set of *duplicate positions*: indices $ i $ such that $ a_i $ appears more than once in $ A $.  \n\n**Constraints**  \n1. $ |F| = |D| = q $, where $ q $ is the minimum number of changes required.  \n2. Each element in $ A $ must be replaced at most once.  \n3. Replacements must assign each missing value in $ F $ to exactly one duplicate position in $ D $.  \n\n**Objective**  \nMinimize $ q = |F| $, and among all ways to achieve this minimum, find the lexicographically minimal permutation $ P = (p_1, p_2, \\dots, p_n) $ such that:  \n- $ p_i = a_i $ if $ a_i $ appears exactly once in $ A $,  \n- $ p_i \\in F $ if $ i \\in D $,  \n- Each value in $ F $ is used exactly once,  \n- The sequence $ P $ is lexicographically minimal.  \n\n**Output**  \n1. $ q = |F| $  \n2. The lexicographically minimal permutation $ P $ satisfying the above.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF864D","tags":["greedy","implementation","math"],"sample_group":[["4\n3 2 2 3","2\n1 2 4 3"],["6\n4 5 6 3 2 1","0\n4 5 6 3 2 1"],["10\n6 8 4 6 7 1 6 3 4 5","3\n2 8 4 6 7 1 9 3 10 5"]],"created_at":"2026-03-03 11:00:39"}}