codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.