Logo Daimayuan Online Judge

Home

时间限制:1 s 空间限制:128 MB

#465. 订单编号

附加文件 统计

小缘开了一家公司,生意很好,每天都会收到很多订单,自动交易系统会自动给这些订单生成没有重复的订单编号。但是有一天,系统出现了未知的错误,导致当天的订单编号可能有重复的,这可把小缘急坏了。你可以帮助小缘按照规则给这些订单重新编号吗?

按照时间先后顺序给出 $N$ 个正整数作为原订单编号,你需要按照规则依次赋予这些订单新的编号,对于任意一个订单,要找到大于等于其原订单编号且未被使用过的(没有被之前的订单作为新的订单编号)的最小整数,作为它的新订单编号。

例如: 原订单编号依次为1 2 3 1,则新订单编号应该为1 2 3 4 (前3个订单的原订单编号都没有使用过,所以用其原订单编号即可,对于第四个订单,原订单编号为1,而1, 2, 3都已经被使用过,所以新订单编号为4)。

输入格式

第一行输入一个整数 $N$ $(1 \leq N \leq 5 \times 10^5)$。

第二行输入 $N$ 个数 $a_i$ $(1 \leq a_i \leq 10^9)$ 作为原订单编号。

输出格式

输出一行,包含 $N$ 个整数为新的订单编号。

样例输入1

6
2 3 4 1 1 1

样例输出1

2 3 4 1 5 6

样例输入2

3
1000000000 1000000000 1000000000

样例输出2

1000000000 1000000001 1000000002

样例输入3

6
4 5 1 2 1 1

样例输出3

4 5 1 2 3 6