题目描述

垒球很喜欢一个叫迷你某·萨菲克斯的题，并且很崇拜这题的出题人，所以出了个差不多的题。

给定一个长度为 $n$ 的序列 $a_1,\ldots,a_n$，请构造一个字典序最大的长度为 $n$ 的字符串 $w$，使得：

• $w$ 的每个字符是 $1$ 到 $n$ 的整数，字符的大小顺序为 $1$ 最小 $n$ 最大；

• $w$ 的长度为 $i$ 的前缀的字典序最大的后缀长度恰为 $a_i$。

请输出这样的 $w$，或报告无解。

本题单个测试点包含多组数据。

输入格式

第一行：一个整数 $T$，表示数据组数。

接下来依次输入 $T$ 组数据，对于每组数据：

第一行：一个整数 $n$。

第二行：$n$ 个整数 $a_1,\ldots,a_n$。

输出格式

对于每组数据：

若无解，只输出一行一个 $-1$。

若有解，则输出一行 $n$ 个整数，表示你给出的 $w$。

6
3
1 1 1
3
1 1 2
3
1 1 3
3
1 2 1
3
1 2 2
3
1 2 3

1 2 3
2 3 3
-1
2 2 3
-1
3 3 3

提示

【样例解释】

字符串 $1,2,3$ 的每个前缀的最大后缀长度恰好为 $1,1,1$，且是满足这个条件的字典序最大的字符串。

字符串 $2,3,3$ 的每个前缀的最大后缀长度恰好为 $1,1,2$，且是满足这个条件的字典序最大的字符串。

不存在一个字符串，每个前缀的最大后缀长度恰好为 $1,1,3$。

字符串 $2,2,3$ 的每个前缀的最大后缀长度恰好为 $1,2,1$，且是满足这个条件的字典序最大的字符串。

不存在一个字符串，每个前缀的最大后缀长度恰好为 $1,2,2$。

字符串 $3,3,3$ 的每个前缀的最大后缀长度恰好为 $1,2,3$，且是满足这个条件的字典序最大的字符串。

---

【评分方式】

每个测试点的分数等于其中所有测试数据分数的最小值。一个测试数据的分数由以下方式确定：

如果你的输出格式错误（即不符合输出格式的要求），则不能得分。

否则，如果你正确判定了是否有解（即在无解的数据输出 $-1$，有解的数据输出了 $n$ 个 $[1,n]$ 中的数），则可以获得 $20\%$ 的分数。

在此基础上，如果该测试点无解，或者有解且你输出的是一组合法解（未必是字典序最大的），则可以再获得 $30\%$ 的分数。

在此基础上，如果该测试点无解，或者有解且你输出的是字典序最大的解，则可以再获得 $50\%$ 的分数。

---

【数据范围】

对于全部数据：$1\leq T\leq 10000$，$1 \le n \le 4 \times 10 ^ 6$，$\sum n\leq 4\times 10^6$，$1\leq a_i\leq i$。

子任务编号	$\sum n\leq$	特殊性质	分值
$\text{Subtask 1}$	$4\times 10^6$	保证无解	$1$
$\text{Subtask 2}$	$4\times 10^5$	保证有解	$29$
$\text{Subtask 3}$	$4\times 10^6$	无	$70$

---

【提示】

请使用较快速的输入输出方式。

---