Problem Description

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.

Input Format

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$.

Output Format

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.

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

Hint

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$.

Hint

Please use fast input/output methods.

Translated by ChatGPT 5