시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB1000.000%

문제

Koishi gives you an integer array $B$ of length $n$ satisfying $1 \leq B_1 \leq B_2 \leq \ldots \leq B_n \leq n + 1$.

Let $S(T)$ denote the set of numbers that appear in array $T$. Koishi asks you whether an array $A$ of length $n$ exists such that, for any $l$ and $r$ such that $1 \leq l \leq r \leq n$, the equality $S(A[l,r]) = S(A[1,n])$ holds if and only if $r \ge B_l$. If so, please construct an array $A$ that satisfies the condition above.

Here, $A[l,r]$ represents the sub-array of $A$ formed by $A_l, A_{l+1}, \ldots, A_{r}$.

You can only use integers from $0$ to $10^9$ in the array. It can be shown that, if a solution exists, then there also exists a solution satisfying this condition.

Notice: If there exists such an index $i$ ($1 \leq i \leq n$) that $B_i < i$ holds, the required $A$ must not exist.

입력

The first line contains an integer $T$ ($1 \leq T \leq 6 \cdot 10^4$), the number of test cases. Then $T$ test cases follow.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$), the length of array $B$ (and $A$).

The next line contains $n$ integers $B_1, B_2, \ldots, B_n$ ($1 \leq B_1 \leq B_2 \leq \ldots \leq B_n \leq n + 1$), the array that Koishi gives you.

It is guaranteed that $\sum n \leq 2.6 \cdot 10^6$.

출력

For each test case, print one line. If such an array $A$ doesn't exist, output $-1$. Otherwise, you should output $n$ numbers: the array $A$ consisting of integers in the range from $0$ to $10^9$. If there are several possible solutions, print any one of them.

예제 입력 1

3
4
3 3 5 5
7
4 6 6 7 8 8 8
5
2 3 4 4 6

예제 출력 1

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