You are given an array B containing N integers, each of which is either -1 or a non-negative integer. Construct any integer array A of length N such that:
0 ≤ A_{i} ≤ 10^{9} for every 1 ≤ i ≤ N
If B_{i} ≥ 0, A must satisfy mex(A_{1}, A_{2}, \ldots, A_{i}) = B_{i}
Otherwise, B_{i} = -1, which means there is no constraint on mex(A_{1}, A_{2}, \ldots, A_{i})

If there does not exist any array satisfying the constraints, print -1 instead.

Note: The mex of a set of non-negative integers is the smallest non-negative integer that does not belong to it. For example, mex(1, 2, 3) = 0, mex(0, 2, 4, 1) = 3, and mex(0, 0, 0) = 1.

------ Input Format ------ 

- The first line of input contains an integer T, denoting the number of testcases. The description of T testcases follows.
- The first line of each testcase contains a single integer N.
- The second line of each testcase contains N space-separated integers B_{1}, B_{2}, \ldots, B_{N}.

------ Output Format ------ 

For each testcase, output the required answer on a new line: -1 if no valid array exists, or N space-separated integers denoting the elements of any valid array A. The elements of A must satisfy 0 ≤ A_{i} ≤ 10^{9}.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$-1 ≤ B_{i} ≤ 10^{5}$
- The sum of $N$ across all testcases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
7
0 -1 2 -1 5 -1 -1
3
2 -1 -1
----- Sample Output 1 ------ 
1 3 0 4 2 6 5
-1
----- explanation 1 ------ 
Test case $1$: We have $A = [1, 3, 0, 4, 2, 6, 5]$. Let $C_{i} = mex(A_{1}, A_{2}, \ldots, A_{i})$. Then, it can be seen that $C = [0, 0, 2, 2, 5, 5, 7]$, which matches $B$ at all positions where $B_{i} ≥ 0$.

Test case $2$: It can be shown that no array $A$ exists that satisfies the given constraints.

Difficulty: HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
from collections import defaultdict
case = int(input())
for t in range(case):
	length = int(input())
	arr = list(map(int, input().split()))
	count = defaultdict(int)
	minim = -1
	for i in range(length):
		if arr[i] != -1:
			if arr[i] > i + 1 or arr[i] < minim:
				print(-1)
				break
			else:
				minim = arr[i]
				count[arr[i]] += 1
	else:
		smallest = 0
		ans = [None] * length
		i = 0
		next = -1
		while i < length:
			if next != -1:
				if next == smallest:
					smallest += 1
				ans[i] = next
				next = -1
				if arr[i] != -1:
					count[arr[i]] -= 1
					if count[arr[i]] == 0:
						next = arr[i]
				i += 1
			elif count[smallest] == 0:
				ans[i] = smallest
				if arr[i] != -1:
					count[arr[i]] -= 1
					if count[arr[i]] == 0:
						next = arr[i]
				i += 1
				smallest += 1
			else:
				smallest += 1
		print(' '.join(map(str, ans)))


t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	if any((b[i] > i + 1 for i in range(n))):
		print(-1)
	elif b == [-1] * n:
		print(' '.join(list(map(str, range(0, n)))))
	else:
		flag = True
		mx = -1
		for el in b:
			if el == -1:
				continue
			if mx == -1 or el > mx:
				mx = el
			elif mx != -1 and el < mx:
				flag = False
				break
		if not flag:
			print(-1)
		else:
			(non_occr, vis) = ([], [0] * (n + 1))
			for el in b:
				vis[el] += 1
			for i in range(n + 1):
				if vis[i] == 0:
					non_occr += [i]
			(ind, a) = (0, [0] * n)
			(curr, size) = (non_occr[ind], len(non_occr))
			mx = max(b) + 1
			for i in range(n):
				a[i] = curr
				if b[i] != -1:
					vis[b[i]] -= 1
					if vis[b[i]] == 0:
						curr = b[i]
					else:
						ind += 1
						curr = non_occr[ind] if ind < size else mx
				elif ind + 1 < size:
					ind += 1
					curr = non_occr[ind]
				else:
					curr = mx
			print(' '.join(list(map(str, a))))


import math
from math import floor, ceil

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def isSubsequence(s, t):
	for i in range(0, len(s)):
		try:
			index = t.index(s[i])
		except ValueError:
			return False
		t = t[index + 1:]
	return True
for _ in range(int(input())):
	N = int(input())
	B = list(map(int, input().split()))
	poss = True
	for i in range(N):
		num = B[i]
		vac = i + 1
		if num > -1:
			num -= 1
			if vac > num:
				pass
			else:
				poss = False
				break
	for i in B:
		if i > -1:
			vals = [i]
			break
	so = vals[0]
	for i in range(1, len(B)):
		if B[i] > -1:
			if B[i] >= so:
				so = B[i]
			else:
				poss = False
				break
	if poss:
		A = [-100 for i in range(N)]
		unfilled = []
		maxIndex = {}
		for i in range(len(B)):
			if B[i] > -1:
				maxIndex[B[i]] = i + 1
		for i in range(2 * N):
			if i not in maxIndex:
				unfilled.append(i)
		for x in maxIndex:
			if maxIndex[x] < N:
				A[maxIndex[x]] = x
		currI = 0
		for i in range(len(A)):
			if A[i] == -100:
				A[i] = unfilled[currI]
				currI += 1
		print(' '.join([str(i) for i in A]))
	else:
		print(-1)


def check(n, a):
	ar = []
	mx = -1
	for i in range(n):
		if a[i] != -1:
			if a[i] < mx:
				return -1
			if a[i] > i + 1:
				return -1
			mx = max(mx, a[i])
			ar.append([i, a[i]])
	data = [i for i in range(n + 1)]
	for i in range(len(ar) - 1, -1, -1):
		val1 = data[ar[i][0] + 1]
		data[ar[i][0] + 1] = data[ar[i][1]]
		data[ar[i][1]] = val1
	return data
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sharma = check(n, a)
	if sharma == -1:
		print(-1)
	else:
		print(*sharma[0:n])


t = int(input())
while t:
	t -= 1
	n = int(input())
	b = list(map(int, input().split()))
	c = [0] * (10 ** 5 + 3)
	a = []
	temp = -1
	flag = 1
	for i in range(n):
		if b[i] != -1:
			if b[i] - 1 > i:
				flag = 0
				break
			if b[i] >= temp:
				temp = b[i]
			elif b[i] < temp:
				flag = 0
				break
	if flag:
		for i in range(n):
			if b[i] != -1:
				c[b[i]] += 1
		k = 0
		temp = 0
		for i in range(n):
			if c[temp] == 0:
				a.append(temp)
				c[temp] = 1
				if b[i] != -1:
					temp = b[i]
					c[temp] -= 1
			elif b[i] != -1:
				temp = b[i]
				while c[k]:
					k += 1
				a.append(k)
				c[k] = 1
				c[temp] -= 1
			else:
				while c[k]:
					k += 1
				a.append(k)
				c[k] = 1
		print(*a)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	s = [int(x) for x in input().split()]
	flag = 0
	max1 = -1
	for i in range(n):
		if s[i] > i + 1:
			flag = 1
			break
		if s[i] < max1 and s[i] != -1:
			flag = 1
			break
		max1 = max(s[i], max1)
	if flag == 1:
		print(-1)
	else:
		ans = [i for i in range(n + 1)]
		ar = []
		for i in range(n):
			if s[i] != -1:
				ar.append([i, s[i]])
		for i in range(len(ar) - 1, -1, -1):
			temp = ans[ar[i][0] + 1]
			ans[ar[i][0] + 1] = ans[ar[i][1]]
			ans[ar[i][1]] = temp
		print(*ans[0:n])


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	last_no = arr[0]
	ans = [-1 for x in range(n + 1)]
	used = [False for x in range(n + 1)]
	for i in range(n - 1, -1, -1):
		if arr[i] != -1 and used[arr[i]] == False:
			ans[i + 1] = arr[i]
			used[arr[i]] = True
	j = 0
	for i in range(n + 1):
		if ans[i] != -1:
			continue
		while used[j] == True:
			j += 1
		ans[i] = j
		j += 1
	used = [False for x in range(n + 1)]
	lastMex = 0
	for i in range(n):
		used[ans[i]] = True
		if arr[i] != -1:
			for j in range(lastMex, i + 1):
				if used[j] == False:
					lastMex = j
					break
			else:
				lastMex = i + 1
			if lastMex != arr[i]:
				print(-1)
				break
	else:
		ans = ans[:-1]
		if len(set(ans)) == n and ans.count('-1') == 0:
			for a in ans:
				print(a, end=' ')
			print()
		else:
			print(-1)


for _ in range(int(input())):
	n = int(input())
	mex = list(map(int, input().split()))
	remmex = {}
	flag = False
	for i in range(n):
		if mex[i] > i + 1:
			print(-1)
			flag = True
			break
		if mex[i] != -1:
			if mex[i] not in remmex:
				remmex[mex[i]] = 1
			else:
				remmex[mex[i]] += 1
	if flag:
		continue
	resarr = []
	used = set()
	currmin = 0
	for i in range(n):
		j = currmin
		while j in remmex or j in used:
			j += 1
		resarr.append(j)
		used.add(j)
		if mex[i] != -1:
			if remmex[mex[i]] == 1:
				del remmex[mex[i]]
			else:
				remmex[mex[i]] -= 1
		while currmin in used:
			currmin += 1
	print(*resarr)


import sys
import math
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline

def dist(x1, x2, y1, y2):
	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def get_power(n):
	i = 1
	p = -1
	while i <= n:
		i = i * 2
		p += 1
	return p

def solve(t):
	n = readInts()
	ar = readList()
	ind = {}
	for i in range(n):
		num = ar[i]
		if num - 1 > i:
			print(-1)
			return None
		if num != -1:
			ind[num] = i
	res = []
	rem = [x for x in range(n + 1)]
	for i in range(n):
		for j in range(len(rem)):
			r = rem[j]
			if r not in ind or ind[r] < i:
				res.append(r)
				rem.pop(j)
				break
	print(*res)

def main():
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


import sys
import math
input = lambda : sys.stdin.readline().rstrip('\r\n')
import heapq
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = False
	for i in range(n):
		if arr[i] > i + 1:
			flag = True
			break
	if flag:
		print(-1)
		continue
	q = []
	count = {}
	for i in arr:
		if i >= 0:
			if i not in count:
				count[i] = 1
			else:
				count[i] += 1
	for i in range(n + 1):
		if i not in count:
			q.append(i)
	heapq.heapify(q)
	ans = []
	for i in arr:
		ans.append(heapq.heappop(q))
		if i >= 0:
			count[i] -= 1
		if i >= 0 and count[i] == 0:
			heapq.heappush(q, i)
			count.pop(i)
	print(' '.join(list(map(str, ans))))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [-1 for i in range(n)]
	d = dict()
	j = 1
	for i in a:
		d[i] = j
		j += 1
	s = set()
	if a[-1] != -1:
		s.add(a[-1])
	for i in d:
		if i != -1 and d[i] != n:
			ans[d[i]] = i
			s.add(i)
	i = 0
	now = 0
	while i < n:
		while now in s:
			now += 1
		if ans[i] != -1:
			i += 1
			continue
		else:
			ans[i] = now
			s.add(now)
	mex = []
	now = 0
	s = set()
	for i in range(n):
		s.add(ans[i])
		while now in s:
			now += 1
		mex.append(now)
	fl = 1
	for i in range(n):
		if a[i] == -1:
			continue
		elif a[i] != mex[i]:
			fl = 0
			break
	if fl == 0:
		print(-1)
	else:
		print(*ans)