codeforces#P1364C. Ehab and Prefix MEXs
Ehab and Prefix MEXs
Description
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.
Input
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$.
Output
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.
Samples
3
1 2 3
0 1 2
4
0 0 0 2
1 3 4 0
3
1 1 3
0 2 1
Note
In the second test case, other answers like $[1,1,1,0]$, for example, are valid.