缺失编号记录

ID: 1064

传统题

1000ms

256MiB

难度: 8

上传者:

题目描述

某套编号记录系统会依次接收 $n$ 个非负整数，并将它们按照接收顺序组成序列 $B$ 。

每接收一个整数后，系统都会检查当前已经出现过的所有编号，并记录其中最小的、尚未出现的非负整数。

现在给出系统在每个时刻记录的结果序列 $A$ 。你需要构造一个长度为 $n$ 的非负整数序列 $B$ ，使得对于每个位置 $i$ ，序列 $B$ 的前 $i$ 个数中，最小的未出现非负整数恰好为 $A_i$ 。

也就是说，对于每个 $1\leq i\leq n$ ，均应满足：

$A_i=\operatorname{mex}(\{B_1,B_2,\ldots,B_i\})$

其中， $\operatorname{mex}$ 表示一个整数集合中最小的、没有在集合中出现的非负整数。

如果有多种符合要求的序列 $B$ ，输出任意一种即可。

第一行包含一个整数 $n$ ，表示序列的长度。

第二行包含 $n$ 个整数 $A_1,A_2,\ldots,A_n$ ，表示系统在各个时刻记录的结果。

输入保证：

如果不存在满足要求的序列 $B$ ，输出：

-1

否则，输出一行 $n$ 个非负整数 $B_1,B_2,\ldots,B_n$ ，表示构造出的序列。

如果存在多个合法答案，输出任意一个即可。

5
0 1 1 3 3

2 0 4 1 5

6
1 1 2 2 5 5

0 3 1 4 2 6

7
0 0 0 4 4 6 6

1 3 2 0 5 4 7