思路

• 核心：为每个位置$i$找到不小于初值$A_i$的、最小的未被使用的整数。
• 数据结构：使用“下一个可用位置”并查集（路径压缩）映射，记映射$parent[x]$表示“从$x$开始的下一个候选位置”。当某个数$y$被占用后，设$parent[y]=y+1$。
• 操作：对每个$A_i$，执行带路径压缩的查找$find(A_i)$得到最小可用的$y\ge A_i$，将其放入答案并标记$parent[y]=y+1$。
• 正确性：路径压缩保证每次返回的是当前$\ge A_i$的最小未用值；按序处理并立即占用，确保最终全局唯一且每个位置增加量最小。
• 复杂度：均摊时间复杂度为$O(N\,\alpha(U))$，其中$U$为值域上界（约为$\max(A_i)+N$），空间复杂度为$O(\text{已占用的不同值个数})$。

C++

题目内容

小明被分配到一个生成不重复元素数组的任务，对于给定一个长度为$N$的数组 $A=[A1,A2,.…,AN]$，数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改$A2,A3,…,AN$。

当修改$Ai$时，小明会检查$Ai$是否在$A1$~$Ai-1$中出现过。如果出现过，则小明会给$Ai$加上$1$;如果新的$Ai$仍在之前出现过，小明会持续给$Ai$加$1$，直到$Ai$没有在$A1$ ~$Ai-1$中出现过。

当$AN$也经过上述修改之后，显然$A$数组中就没有重复的整数了。

现在给定初始的$A$数组，请你帮小明计算出最终的$A$数组。

输入描述

第一行包含一个整数$N$。

第二行包含$N$个整数$A1,A2,…,AN$。

其中，$1≤N≤10^5,1≤Ai≤10^6$

输出描述

输出$N$个整数，依次是最终的$A1,A2,...,AN$。

样例1

输入

5
2 1 1 3 4

输出

2 1 3 4 5