← 返回题目列表

Codeforces · 1364/C

C. Ehab 和前缀 MEX

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

给定一个长度为 $$$n$$$ 的数组 $$$a$$$,找到另一个长度为 $$$n$$$ 的数组 $$$b$$$,使得:

- 对于每个 $$$i$$$ $$$(1 \le i \le n)$$$ $$$MEX(\{b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_i\})=a_i$$$。

一组整数的 $$$MEX$$$ 是不属于该组的最小非负整数。

如果这样的数组不存在,请确定它。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1$$$、$$$a_2$$$、$$$\ldots$$$、$$$a_n$$$ ($$$0 \le a_i \le i$$$) — 数组 $$$a$$$ 的元素。保证 $$$a_i \le a_{i+1}$$$ 对于 $$$1\le i < n$$$。

输出

如果没有这样的数组,则打印包含 $$$-1$$$ 的单行。

否则,打印包含 $$$n$$$ 整数 $$$b_1$$$、$$$b_2$$$、$$$\ldots$$$、$$$b_n$$$ 的单行 ($$$0 \le b_i \le 10^6$$$)

如果有多个答案,请打印其中一个。

示例

输入 #1

3
1 2 3

输出 #1

0 1 2

输入 #2

4
0 0 0 2

输出 #2

1 3 4 0

输入 #3

3
1 1 3

输出 #3

0 2 1

注意

在第二个测试用例中,其他答案(例如 $$$[1,1,1,0]$$$)是有效的。