橙垒球

垒球很喜欢一个叫迷你某·萨菲克斯的题，并且很崇拜这题的出题人，所以出了个差不多的题。 给定一个长度为 $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$ | --- **【提示】** 请使用较快速的输入输出方式。 ---