1227B.md (2403B)
1 Source: https://codeforces.com/problemset/problem/1227/B 2 3 B. Box 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 Permutation $p$ is a sequence of integers $p=[p_1, p_2, \dots, p_n]$, consisting of $n$ distinct (unique) positive integers between $1$ and $n$, inclusive. For example, the following sequences are permutations: $[3, 4, 1, 2]$, $[1]$, $[1, 2]$. The following sequences are not permutations: $[0]$, $[1, 2, 1]$, $[2, 3]$, $[0, 1, 2]$. 22 23 The important key is in the locked box that you need to open. To open the box you need to enter secret code. Secret code is a permutation $p$ of length $n$. 24 25 You don't know this permutation, you only know the array $q$ of prefix maximums of this permutation. Formally: 26 27 * $q_1=p_1$, 28 * $q_2=\max(p_1, p_2)$, 29 * $q_3=\max(p_1, p_2,p_3)$, 30 * ... 31 * $q_n=\max(p_1, p_2,\dots,p_n)$. 32 33 You want to construct any possible suitable permutation (i.e. any such permutation, that calculated $q$ for this permutation is equal to the given array). 34 35 Input 36 37 The first line contains integer number $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow. 38 39 The first line of a test case contains one integer $n$ $(1 \le n \le 10^{5})$ — the number of elements in the secret code permutation $p$. 40 41 The second line of a test case contains $n$ integers $q_1, q_2, \dots, q_n$ $(1 \le q_i \le n)$ — elements of the array $q$ for secret permutation. It is guaranteed that $q_i \le q_{i+1}$ for all $i$ ($1 \le i \lt n$). 42 43 The sum of all values $n$ over all the test cases in the input doesn't exceed $10^5$. 44 45 Output 46 47 For each test case, print: 48 49 * If it's impossible to find such a permutation $p$, print "-1" (without quotes). 50 * Otherwise, print $n$ distinct integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). If there are multiple possible answers, you can print any of them. 51 52 Example 53 54 Input 55 56 ``` 57 4 58 5 59 1 3 4 5 5 60 4 61 1 1 3 4 62 2 63 2 2 64 1 65 1 66 ``` 67 68 Output 69 70 ``` 71 1 3 4 5 2 72 -1 73 2 1 74 1 75 ``` 76 77 Note 78 79 In the first test case of the example answer $[1,3,4,5,2]$ is the only possible answer: 80 81 * $q_{1} = p_{1} = 1$; 82 * $q_{2} = \max(p_{1}, p_{2}) = 3$; 83 * $q_{3} = \max(p_{1}, p_{2}, p_{3}) = 4$; 84 * $q_{4} = \max(p_{1}, p_{2}, p_{3}, p_{4}) = 5$; 85 * $q_{5} = \max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5$. 86 87 It can be proved that there are no answers for the second test case of the example.