Box

题意翻译

## 题目描述 排列 $ p $ 是一个 $ p=[p_1, p_2, \dots, p_n] $ 的广泛数列,包括 $ n $ 个各不相同（唯一）的从1到n的正整数。比如，这些数列是排列：$ [3, 4, 1, 2] $ , $ [1] $ , $ [1, 2] $。这些不是排列：$ [0] $ , $ [1, 2, 1] $ , $ [2, 3] $ , $ [0, 1, 2] $ 。 重要的钥匙在一个需要你打开的锁上的盒子里。你需要输入密码来打开它。密码是一个长度为 $n$ 的序列。 你不知道这个排列，你只知道这个排列前缀的最大值。定义如下： - $ q_1=p_1 $ , - $ q_2=\max(p_1, p_2) $ , - $ q_3=\max(p_1, p_2,p_3) $ , - ... - $ q_n=\max(p_1, p_2,\dots,p_n) $ . 你想要把所有可能的排列都构造出来（即任何这样的排列，使得计算出的 $q$ 与给出的数组相同）。 ## 输入格式 输入的第一行包括一个整数 $ t $ ( $ 1 \le t \le 10^4 $ )，$t$ 为输入中包含的数据组数。接着输入 $t$ 组数据。 一组数据的第一行包含一个整数 $ n $ $ (1 \le n \le 10^{5}) $，$n$ 为排列 $p$ 中元素的个数。 一组数据的第二行包含 $n$ 个整数 $ q_1, q_2, \dots, q_n $ $ (1 \le q_i \le n) $ ，为秘密排列的数组 $q$。保证对于每个 $ i $ ( $ 1 \le i < n $ )，均有 $ q_i \le q_{i+1} $ 。 输入中每组数组 $n$ 的总和不超过 $ 10^5 $。 ## 输出格式 对于每组数据，输出： - 如果不可能找到满足的排列 $p$，输出 "-1"（不包括引号） - 否则，输出n个不同的整数 $ p_1, p_2, \dots, p_n $ ( $ 1 \le p_i \le n $ )。如果有多组可能的答案，你可以输出任何一组。 ## 样例提示 样例的第一组数据中， $ [1,3,4,5,2] $ 是唯一一组可能的答案: - $ q_{1} = p_{1} = 1 $ ; - $ q_{2} = \max(p_{1}, p_{2}) = 3 $ ; - $ q_{3} = \max(p_{1}, p_{2}, p_{3}) = 4 $ ; - $ q_{4} = \max(p_{1}, p_{2}, p_{3}, p_{4}) = 5 $ ; - $ q_{5} = \max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5 $ . 可以证明样例的第二组数据没有答案。 翻译来自 @[carreye](https://www.luogu.com.cn/user/188360)

题目描述

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] $ . 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 $ . You don't know this permutation, you only know the array $ q $ of prefix maximums of this permutation. Formally: - $ q_1=p_1 $ , - $ q_2=\max(p_1, p_2) $ , - $ q_3=\max(p_1, p_2,p_3) $ , - ... - $ q_n=\max(p_1, p_2,\dots,p_n) $ . 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).

输入输出格式

输入格式

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. 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 $ . 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 < n $ ). The sum of all values $ n $ over all the test cases in the input doesn't exceed $ 10^5 $ .

输出格式

For each test case, print: - If it's impossible to find such a permutation $ p $ , print "-1" (without quotes). - 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.

输入输出样例

输入样例 #1

4
5
1 3 4 5 5
4
1 1 3 4
2
2 2
1
1

输出样例 #1

1 3 4 5 2 
-1
2 1 
1 

说明

In the first test case of the example answer $ [1,3,4,5,2] $ is the only possible answer: - $ q_{1} = p_{1} = 1 $ ; - $ q_{2} = \max(p_{1}, p_{2}) = 3 $ ; - $ q_{3} = \max(p_{1}, p_{2}, p_{3}) = 4 $ ; - $ q_{4} = \max(p_{1}, p_{2}, p_{3}, p_{4}) = 5 $ ; - $ q_{5} = \max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5 $ . It can be proved that there are no answers for the second test case of the example.