Permutation $p$ is a sequence of integers $p=[p_1, p_2, \dots, p_n]$, consisting of $n$ distinct (unique) positive integers between $1$ and $n$, inclusive. For example, the following sequences are permutations: $[3, 4, 1, 2]$, $[1]$, $[1, 2]$. The following sequences are not permutations: $[0]$, $[1, 2, 1]$, $[2, 3]$, $[0, 1, 2]$.

The important key is in the locked box that you need to open. To open the box you need to enter secret code. Secret code is a permutation $p$ of length $n$. 

You don't know this permutation, you only know the array $q$ of prefix maximums of this permutation. Formally:  $q_1=p_1$,  $q_2=\max(p_1, p_2)$,  $q_3=\max(p_1, p_2,p_3)$,  ...  $q_n=\max(p_1, p_2,\dots,p_n)$. 

You want to construct any possible suitable permutation (i.e. any such permutation, that calculated $q$ for this permutation is equal to the given array).


-----Input-----

The first line contains integer number $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.

The first line of a test case contains one integer $n$ $(1 \le n \le 10^{5})$ — the number of elements in the secret code permutation $p$.

The second line of a test case contains $n$ integers $q_1, q_2, \dots, q_n$ $(1 \le q_i \le n)$ — elements of the array $q$ for secret permutation. It is guaranteed that $q_i \le q_{i+1}$ for all $i$ ($1 \le i < n$).

The sum of all values $n$ over all the test cases in the input doesn't exceed $10^5$.


-----Output-----

For each test case, print:  If it's impossible to find such a permutation $p$, print "-1" (without quotes).  Otherwise, print $n$ distinct integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). If there are multiple possible answers, you can print any of them. 


-----Example-----
Input
4
5
1 3 4 5 5
4
1 1 3 4
2
2 2
1
1

Output
1 3 4 5 2 
-1
2 1 
1 



-----Note-----

In the first test case of the example answer $[1,3,4,5,2]$ is the only possible answer:  $q_{1} = p_{1} = 1$;  $q_{2} = \max(p_{1}, p_{2}) = 3$;  $q_{3} = \max(p_{1}, p_{2}, p_{3}) = 4$;  $q_{4} = \max(p_{1}, p_{2}, p_{3}, p_{4}) = 5$;  $q_{5} = \max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5$. 

It can be proved that there are no answers for the second test case of the example.

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for faw in range(t):
    n = int(input())
    a = [0] + list(map(int,input().split()))
    nun = []
    ans = []
    f = True
    for i in range(1, n + 1):
        if a[i] == a[i-1]:
            if len(nun) == 0:
                f = False
                break
            else:
                ans.append(nun.pop())
        else:
            ans.append(a[i])
            for i in range(a[i - 1] + 1, a[i]):
                nun.append(i)
    if f:
        print(*ans)
    else:
        print(-1)


t=int(input())
for i in range(t):
    n=int(input())
    a=[int(x) for x in input().split()]
    b=[0] * n
    m=0
    c=set(range(1, n+1))
    for i in range(n):
        if a[i] > m:
            b[i] = a[i]
            m = a[i]
            c.discard(a[i])
    c=sorted(c)
    j=0
    for i in range(n):
        if b[i] == 0:
            b[i] = c[j]
            j+=1
            if b[i] > a[i]:
                print(-1)
                break
    else:
        print(*b)


t = int(input())
for z in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    ret = [0 for i in range(n)]
    was = set()
    can = set([i for i in range(1, n + 1)])
    for i in range(n):
        x = arr[i]
        if not x in was:
            ret[i] = x
            was.add(x)
    left = sorted(list(can - was), reverse=True)
    for i in range(n):
        if not left:
            break
        x = left[-1]
        if not ret[i]:
            ret[i] = x
            left.pop()
    mx = ret[0]
    flag = True
    for i in range(n):
        mx = max(mx, ret[i])
        if mx != arr[i]:
            flag = False
            break
    if flag:
        print(*ret)
    else:
        print(-1)


n = int(input())
for i in range(n):
    k = int(input())
    used = [0]*k
    a = list(map(int, input().split()))
    p = 0
    ans = [0]*k
    for i in range(k):
        if a[i] != p:
            ans[i] = a[i]
            used[a[i]-1] = 1
        p = a[i]
    t = 0
    flag = 0
    for i in range(k):
        if ans[i] == 0:
            while used[t] == 1 and t < a[i]:
                t +=1
            if t == a[i]:
                flag = 1
                break
            else:
                used[t] = 1
                ans[i] = t+1
    if flag == 1:
        print(-1)
    else:
        print(*ans)


t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = [0] * (n + 2)
    c = 1
    d = a[0]
    ans = [a[0]]
    b[a[0]] = 1
    for i in range(1, len(a)):
        if a[i] == a[i - 1]:
            while b[c] != 0:
                c += 1
            if c > a[i]:
                ans = -1
                break
            else:
                b[c] = 1
                ans.append(c)
        else:
            ans.append(a[i])
            b[a[i]] = 1
    if ans == -1:
        print(ans)
    else:
        print(*ans)
    
    


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(ii) for ii in input().split()]
	b = [0 for ii in range(n)]
	was = [0 for ii in range(n + 1)]
	minimum = 1
	for j in range(n):
		if j == 0 or a[j] != a[j - 1]:
			was[a[j]] = 1
			b[j] = a[j]
		else:
			while was[minimum] == 1:
				minimum += 1
			if minimum > a[j]:
				minimum = -1
				break
			b[j] = minimum
			was[minimum] = 1
	if minimum == -1:
		print (-1)
	else:
		for j in b:
			print(j, end = ' ')
		print ('')

a =  int(input())
Ans = []
for i in range(a):
    B = []
    x = int(input())
    A = list(map(int, input().split()))
    C = []
    for j in range(1, len(A) + 1):
        C.append([j, 0])
    k = 1
    n = 0
    for j in range(len(A)):
        if A[j] >k:
            B.append(A[j])
            k = A[j]
            C[A[j] - 1][1] = 1
        else:
            while C[n][1] == 1:
                n += 1
            C[n][1] = 1
            B.append(n + 1)
    b0 = B[0]
    Tr = True
    for j in range(len(B)):
        b0 = max(b0, B[j])
        if A[j] != b0:
            Tr = False
    if Tr:
        Ans.append(B)
    else:
        Ans.append([-1])
    #Ans.append(B[-1])
for b in Ans:
    print(*b)


t = int(input())
for request in range(t):
    n = int(input())
    result, initial = list(map(int, input().split())), []
    box, flag = [], True
    initial.append(result[0])
    for d in range(1, result[0]):
                box.append(d)
    for i in range(1, n):
        if result[i - 1] < result[i]:
            initial.append(result[i])
            for d in range(result[i - 1] + 1, result[i]):
                box.append(d)
        else:
            try:
                initial.append(box.pop())
            except:
                flag = False
                break
    if flag:
        print(*initial)
    else:
        print(-1)

t = int(input())
for tt in range(t):
    n = int(input())
    ent = list(map(int,input().split()))
    used = [0]*(n+1)
    mnex = 1
    mx = 0
    ans = []
    ansex = True
    for i in range(n):
        if ent[i] > mx:
            mx = ent[i]
            if used[mx] == 0:
                ans.append(mx)
                used[mx] = 1
            else:
                ansex = False
                break
        else:
            while used[mnex] == 1:
                mnex += 1
            if mnex <= mx:
                used[mnex]=1
                ans.append(mnex)
                mnex+=1
            else:
                ansex = False
                break
    if ansex:
        print(*ans)
    else:
        print(-1)
                







t=int(input())
for i in range(t):
    n=int(input())
    q=list(map(int,input().split()))
    pr=[0]*n
    ans=[0]*n
    ans[0]=q[0]
    sh=0
    s=set([q[0]])
    for i in range(1,n):
        if q[i]==q[i-1]:
            pr[i]=pr[i-1]
            sh+=1
        else:
            pr[i]=i
            ans[i]=q[i]
            s.add(q[i])
    steak=[]
    for i in range(n,0,-1):
        if i not in s:
            steak.append(i)
    tr=True
    for i in range(n):
        if ans[i]==0:
            x=steak.pop()
            if x<q[pr[i]]:
                ans[i]=x
            else:
                tr=False
                break
    if tr:
        print(*ans)
    else:
        print(-1)


a = int(input())
for i in range(a):
    b = int(input())
    l = list(map(int, input().split()))
    k = []
    t = [i for i in range(b + 1)]
    k.append(l[0])
    last = k[0]
    j = 0
    t[last] = 0
    for i in l[1:]:
        if i != last:
            last = i
            k.append(last)
            t[last] = 0
        else:
            while t[j] == 0:
                j += 1
            k.append(t[j])
            j += 1
    ch = [k[0]]
    for i in k[1:]:
        ch.append(max(ch[-1], i))
    if l != ch:
        print(-1)
    else:
        print(*k)

t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    used = []
    for i in range(n):
        used.append(False)
    p = [str(a[0])]
    used[a[0] - 1] = True
    ans = 1
    now = 0
    for i in range(1, n):
        while now < n and used[now]:
            now += 1
        if a[i] > a[i - 1]:
            p.append(str(a[i]))
            if used[a[i] - 1]:
                ans = 0
                break
            used[a[i] - 1] = True
        else:
            if now + 1 > a[i] or used[now]:
                ans = 0
                break
            used[now] = True
            p.append(str(now + 1))
    if ans:
        print(" ".join(p))
    else:
        print(-1)

from collections import deque
for i in range(int(input())):
    n = int(input())
    h = deque([i+1 for i in range(n)])
    used = [False]*n
    ans = [0]*n
    c = list(map(int,input().split()))
    ans[0] = c[0]
    used[c[0]-1] = True
    f = True
    for i in range(n):
        if i+1>c[i]:
            f = False
    if not f:
        print(-1)
        continue
    for i in range(n-1):
        if c[i+1]!=c[i]:
            ans[i+1] = c[i+1]
        else:
            x = h.popleft()
            while used[x-1]:
                x = h.popleft()
            ans[i+1] = x
        used[ans[i+1] - 1] = True
    print(*ans)

t=int(input())
for magic in range(t):
    n=int(input())
    res=[0 for j in range(n+1)]
    have=[1 for sth in range(n+1)]
    br_p=0
    given=[0]+list(map(int,input().split()))
    for i in range(1,n+1):
        if given[i-1]<given[i]:
            res[i]=given[i]
            have[given[i]]=0
        elif given[i-1]>given[i]:
            br_p=1
            break
    if br_p:
        print(-1)
    else:
        ind_last=1
        for i in range(1,n+1):
            if res[i]==0:
                while have[ind_last]==0:
                    ind_last+=1
                res[i]=ind_last
                ind_last+=1
        for i in range(1,n+1):
            if given[i]<res[i]:
                br_p=1
                break
        if br_p:
            print(-1)
        else:
            print(*res[1:])





t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = [False] * n
    b[a[0] - 1] = True
    k = 0
    res = [a[0]]
    flag = True
    for j in range(1, n):
        if a[j] == a[j - 1]:
            while k < n and b[k]:
                k += 1
            if k + 1 > a[j]:
                flag = False
                break
            res.append(k + 1)
            b[k] = True
        else:
            b[a[j] - 1] = True
            res.append(a[j])
    if flag:
        print(' '.join(map(str, res)))
    else:
        print(-1)

t=int(input())
for g in range(t):
  n=int(input())
  a=list(map(int,input().split()))
  b=list(False for i in range(n))
  flag=False
  count=0
  res=list(range(n))
  for i in range(n):
    if i==0:
      res[i]=a[i]
      b[a[i]-1]=True
    elif a[i]!=a[i-1]:
      res[i]=a[i]
      b[a[i]-1]=True
    else:
      for j in range(count,n):
        if j+1>a[i]:
          flag=True
          count=j
          break
        else:
          if not b[j]:
            res[i]=j+1
            b[j]=True
            count=j
            break
  if flag:
    print(-1)
  else:
    for i in range(n):
      print(res[i],end=' ')
    print()


for __ in range(int(input())):
    n = int(input())
    ar1 = list(map(int, input().split()))
    ar = ar1.copy()
    lol = set()
    for j in range(1, n + 1):
        lol.add(j)
    lol.discard(ar[0])
    for i in range(1, n):
        if ar1[i] > ar1[i - 1]:
            lol.discard(ar1[i])
        else:
            ar[i] = 0
    kek = list(lol)
    kek.sort()
    num = 0
    flag = 0
    for j in range(n):
        if ar[j] == 0:
            ar[j] = kek[num]
            num += 1
        if ar[j] > ar1[j]:
            flag = 1
    if flag == 1:
        print(-1)
    else:
        print(*ar)


for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = [0] * n
    used = [False] * (n + 1)
    ans[0] = a[0]
    used[a[0]] = True
    lst = 1
    ok = True
    for i in range(1, n):
        if a[i] > a[i - 1]:
            ans[i] = a[i]
            used[a[i]] = True
        elif a[i] < a[i - 1]:
            print(-1)
            ok = False
            break
        else:
            while used[lst]:
                lst += 1
            #print(lst)
            if a[i] < lst:
                print(-1)
                ok = False
                break
            else:
                ans[i] = lst
                lst += 1
                used[ans[i]] = True
    if ok:
        for i in range(n):
            print(ans[i], end=' ')
        print()

m = int(input())
for j in range(m):
    n = int(input())
    a = list(map(int, input().split()))
    b = []
    used = [0] * (n + 1)
    t = 1
    b.append(a[0])
    f = True
    used[a[0]] = 1
    for k in range(1, n):
        if a[k] == a[k - 1]:
            while used[t] == 1:
                t += 1                    
            if t < a[k - 1]:
                b.append(t)
                used[t] = 1
                t += 1
            else:
                f = False
                break
        elif a[k] > a[k - 1]:
            b.append(a[k])
            used[a[k]] = 1
        else:
            f = False
            break
    if f:
        print(*b)
    else:
        print(-1)
            


t = int(input())
for i in range(t):
    n = int(input())
    q = list(map(int, input().split()))
    used = set()
    ans = []
    used.add(q[0])
    ans.append(q[0])
    cnt = 1
    flag = False
    for i in range(1, n):
        if q[i] == q[i - 1]:
            while cnt in used:
                cnt += 1
            used.add(cnt)
            if q[i] > cnt:
                ans.append(cnt)
            else:
                flag = True
                break
        else:
            used.add(q[i])
            ans.append(q[i])
    if flag:
        print(-1)
    else:
        print(*ans)

for i in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    q=-1
    t=0
    r=[]
    for i in range(n):
        if a[i]<q or a[i]<i+1:
            t=1
            break
        else:
            q=a[i]
    if t==1:
        print(-1)
    else:
        q=-1
        w=[True]*n
        z=0
        for i in range(n):
            if a[i]>q:
                r.append(a[i])
                w[a[i]-1]=False
                q=a[i]
            else:
                while w[z]==False:
                    z+=1
                r.append(z+1)
                z+=1
        print(*r)


t = int(input())
for i in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    used = [0for i in range(n + 2)]
    ans = []
    minimum = 1
    ans.append(a[0])
    used[a[0]] = 1
    if a[0] == 1:
        minimum = 2
    for i in range(1, len(a)):
        if a[i] != a[i - 1]:
            ans.append(a[i])
            used[a[i]] = 1
            if a[i] == minimum:
                minimum += 1
        else:
            ans.append(minimum)
            used[minimum] = 1
            while used[minimum] == 1:
                minimum += 1
    maximum = 0
    flag = True
    for i in range(len(ans)):
        maximum = max(maximum, ans[i])
        if a[i] != maximum:
            flag = False
    if flag and a[-1] == n:
        print(" ".join(map(str, ans)))
    else:
        print(-1)

t = int(input())

for i in range(t):
    n = int(input())
    q = list(map(int, input().split()))
    used = {q[0]: True}
    seq = [q[0]]

    ks = 1

    for j in range(1, n):
        if q[j] == q[j - 1]:
            for k in range(ks, q[j]):
                if used.get(k) is None:
                    seq.append(k)
                    used[k] = True
                    ks = k + 1
                    break
            else:
                print(-1)
                break
        else:
            used[q[j]] = True
            seq.append(q[j])
    else:
        print(*seq)

w = int(input())
for q in range(w):
    fr = 1
    n = int(input())
    a = list(map(int, input().split()))
    a.append(a[0] - 1)
    e = [1] * (n+1)
    ei = 1
    r = [0] * n
    for i in range(n):
        if a[i] == a[i-1]:
            while e[ei] == 0 and ei < n:
                ei += 1
            if ei > a[i]:
                print(-1)
                fr = 0
                break
            r[i] = ei
            e[ei] = 0
        else:
            if e[a[i]] == 1:
                e[a[i]] = 0
                r[i] = a[i]
            else:
                print(-1)
                fr = 0
                break
    if fr:
        print(*r)