307494: CF1364C. Ehab and Prefix MEXs
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Ehab and Prefix MEXs
题意翻译
### 题目描述 给出一个长度为 $n$ 的序列 $A$,你需要找到一个长度为 $n$ 的序列 $B$,满足 $A_i=mex(\{B_1,B_2,\dots,B_i\})$。 其中 $mex$ 函数的结果是最小的未出现在集合中的非负整数。 ### 输入格式 第一行一个整数 $n$。 之后一行 $n$ 个整数,表示给出的序列 $A$。 保证 $1\le n\le10^5$,$0\le a_i\le i$,对于 $1\le i<n$,$a_i\le a_{i+1}$。 ### 输出格式 如果序列 $B$ 不存在,输出 `-1`。 否则输出一行 $n$ 个整数表示你找到的 $B$,若有多个满足条件的序列,输出任意一个。题目描述
Given an array $ a $ of length $ n $ , find another array, $ b $ , of length $ n $ such that: - for each $ i $ $ (1 \le i \le n) $ $ MEX(\{b_1 $ , $ b_2 $ , $ \ldots $ , $ b_i\})=a_i $ . The $ MEX $ of a set of integers is the smallest non-negative integer that doesn't belong to this set. If such array doesn't exist, determine this.输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the array $ a $ . The second line contains $ n $ integers $ a_1 $ , $ a_2 $ , $ \ldots $ , $ a_n $ ( $ 0 \le a_i \le i $ ) — the elements of the array $ a $ . It's guaranteed that $ a_i \le a_{i+1} $ for $ 1\le i < n $ .
输出格式
If there's no such array, print a single line containing $ -1 $ . Otherwise, print a single line containing $ n $ integers $ b_1 $ , $ b_2 $ , $ \ldots $ , $ b_n $ ( $ 0 \le b_i \le 10^6 $ ) If there are multiple answers, print any.
输入输出样例
输入样例 #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