← 返回题目列表

Codeforces · 864/D

D. 进行排列!

中文机器翻译题面 查看原题

Ivan 有一个由 n 个元素组成的数组。每个元素都是从 1 到 n 的整数。

最近 Ivan 了解了排列及其字典顺序。现在他想要更改(替换)数组中元素的最小数量,使其数组成为排列(即,从 1 到 n 的每个整数在数组中只遇到一次)。如果有多种方法可以做到这一点,他想找到其中字典顺序最小的排列。

因此,最小化更改数量具有第一优先级,词典编纂最小化具有第二优先级。

为了确定这两个排列中哪一个按字典顺序更小,我们比较它们的第一个元素。如果它们相等 - 比较第二个,依此类推。如果我们有两个排列 x 和 y,则如果 xi < yi,则 x 按字典顺序较小,其中 i 是排列 x 和 y 不同的第一个索引。

确定 Ivan 在执行所有更改后将获得的数组。

输入

第一行包含一个整数 n (2 ≤ n ≤ 200 000) — Ivan 数组中的元素数量。

第二行包含整数序列 a1, a2, ..., an (1 ≤ ai ≤ n) — Ivan 数组的描述。

输出

在第一行中打印 q — Ivan 数组中需要更改的最小元素数,以便使他的数组成为排列。在第二行中,打印可以从具有 q 变化的数组中获得的字典顺序最小排列。

示例

输入 #1

4
3 2 2 3

输出 #1

2
1 2 4 3

输入 #2

6
4 5 6 3 2 1

输出 #2

0
4 5 6 3 2 1

输入 #3

10
6 8 4 6 7 1 6 3 4 5

输出 #3

3
2 8 4 6 7 1 9 3 10 5

注意

在第一个示例中,Ivan 需要将位置 1 中的数字 3 替换为数字 1,将位置 3 中的数字 2 替换为数字 4。然后他将得到一个只有两个改变的数字的排列 [1, 2, 4, 3] ——这个排列在所有合适的字典中是最小的。

在第二个示例中,Ivan 不需要更改任何内容,因为他的数组已经是一个排列。