P9395 Orange Baseball

Baseball really likes a problem called Mini Something · Suffix, and also greatly admires the author of that problem, so they made a similar problem. Given a sequence $a_1,\ldots,a_n$ of length $n$, construct a **lexicographically maximum** string $w$ of length $n$ such that: - Each character of $w$ is an integer from $1$ to $n$, and the order of characters is $1$ as the smallest and $n$ as the largest. - For the prefix of $w$ with length $i$, the length of its **lexicographically maximum suffix** is exactly $a_i$. Output such a $w$, or report that there is no solution. This problem contains multiple test cases in a single test point.

The first line contains an integer $T$, which is the number of test cases. Then follow $T$ test cases. For each test case: The first line contains an integer $n$. The second line contains $n$ integers $a_1,\ldots,a_n$.

For each test case: If there is no solution, output one line with a single integer $-1$. If there is a solution, output one line with $n$ integers, representing the string $w$ you constructed.

**Sample Explanation** For the string $1,2,3$, for each prefix, the length of its maximum suffix is exactly $1,1,1$, and it is the lexicographically maximum string satisfying this condition. For the string $2,3,3$, for each prefix, the length of its maximum suffix is exactly $1,1,2$, and it is the lexicographically maximum string satisfying this condition. There does not exist a string such that for each prefix, the length of its maximum suffix is exactly $1,1,3$. For the string $2,2,3$, for each prefix, the length of its maximum suffix is exactly $1,2,1$, and it is the lexicographically maximum string satisfying this condition. There does not exist a string such that for each prefix, the length of its maximum suffix is exactly $1,2,2$. For the string $3,3,3$, for each prefix, the length of its maximum suffix is exactly $1,2,3$, and it is the lexicographically maximum string satisfying this condition. --- **Scoring** The score of each test point equals the minimum score among all testdata within it. The score of a single testdata is determined as follows: If your output format is wrong (i.e., it does not meet the output format requirements), you get no score. Otherwise, if you correctly determine whether a solution exists (i.e., output $-1$ for unsolvable testdata, and output $n$ numbers in $[1,n]$ for solvable testdata), you can get $20\%$ of the score. On this basis, if the test point is unsolvable, or it is solvable and you output a valid solution (not necessarily the lexicographically maximum one), you can get an additional $30\%$ of the score. On this basis, if the test point is unsolvable, or it is solvable and you output the lexicographically maximum solution, you can get an additional $50\%$ of the score. --- **Constraints** For all testdata: $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$. | Subtask ID | $\sum n\leq$ | Special Property | Score | | :----------------: | :------------: | :--------------: | :---: | | $\text{Subtask 1}$ | $4\times 10^6$ | Guaranteed no solution | $1$ | | $\text{Subtask 2}$ | $4\times 10^5$ | Guaranteed solvable | $29$ | | $\text{Subtask 3}$ | $4\times 10^6$ | None | $70$ | --- **Hint** Please use fast input/output methods. ---  Translated by ChatGPT 5