1364C.md (1263B)
1 Source: https://codeforces.com/problemset/problem/1364/C 2 3 C. Ehab and Prefix MEXs 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given an array $a$ of length $n$, find another array, $b$, of length $n$ such that: 22 23 * for each $i$ $(1 \le i \le n)$ $MEX(\{b_1$, $b_2$, $\ldots$, $b_i\})=a_i$. 24 25 The $MEX$ of a set of integers is the smallest non-negative integer that doesn't belong to this set. 26 27 If such array doesn't exist, determine this. 28 29 Input 30 31 The first line contains an integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$. 32 33 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 \lt n$. 34 35 Output 36 37 If there's no such array, print a single line containing $-1$. 38 39 Otherwise, print a single line containing $n$ integers $b_1$, $b_2$, $\ldots$, $b_n$ ($0 \le b_i \le 10^6$) 40 41 If there are multiple answers, print any. 42 43 Examples 44 45 Input 46 47 ``` 48 3 49 1 2 3 50 ``` 51 52 Output 53 54 ``` 55 0 1 2 56 ``` 57 58 Input 59 60 ``` 61 4 62 0 0 0 2 63 ``` 64 65 Output 66 67 ``` 68 1 3 4 0 69 ``` 70 71 Input 72 73 ``` 74 3 75 1 1 3 76 ``` 77 78 Output 79 80 ``` 81 0 2 1 82 ``` 83 84 Note 85 86 In the second test case, other answers like $[1,1,1,0]$, for example, are valid.