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 不需要更改任何内容,因为他的数组已经是一个排列。