Consider an array A consisting of N positive elements. The *frequency array* of A is the array B of size N such that B_{i} = *frequency* of element A_{i} in A.

For example, if A = [4, 7, 4, 11, 2, 7, 7], the *frequency array* B = [2, 3, 2, 1, 1, 3, 3].

You have lost the array A, but fortunately you have the array B.  
Your task is to construct the lexicographically smallest array A such that:
1≤ A_{i} ≤ 10^{5};
The frequency array of A is equal to B.

If no such array A exists, print -1.

Note: Array X is lexicographically smaller than array Y, if X_{i} < Y_{i}, where i is the first index where X and Y differ.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains a single integer N — the size of the array.
- The next line contains N space-separated integers - B_{1}, B_{2}, \ldots, B_{N}, the frequency array.

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

For each test case, output on a new line, N space separated integers - A_{1}, A_{2}, \ldots, A_{N}, the lexicographically smallest array A. If no such array A exists, print -1.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ B_{i} ≤ 10^{5}$
- The sum of $N$ over all test cases won't exceed $10^{6}$.

----- Sample Input 1 ------ 
5
5
2 3 3 3 2
5
1 1 1 1 1
5
5 5 5 5 5
3
1 2 4
8
1 3 2 3 2 2 2 3
----- Sample Output 1 ------ 
1 2 2 2 1
1 2 3 4 5
1 1 1 1 1
-1
1 2 3 2 3 4 4 2

----- explanation 1 ------ 
Test case $1$: The lexicographically smallest array $A$ having the given frequency array $B$ is $A = [1, 2, 2, 2, 1]$. The element $A_{1}$ and $A_{5}$ have frequency $2$ while $A_{2}, A_{3},$ and $A_{4}$ have frequency $3$.

Test case $2$: The lexicographically smallest array $A$ having the given frequency array $B$ is $A = [1, 2, 3, 4, 5]$. Each element in $A$ has frequency $1$.

Test case $3$: The lexicographically smallest array $A$ having the given frequency array $B$ is $A = [1, 1, 1, 1, 1]$. Each element in $A$ has frequency $5$.

Test case $4$: No possible array $A$ exists having the given frequency array.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Sorting

Data structures

Greedy algorithms


Solutions:
import numpy as np

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())

def lexsmall(freqarr):
	for j in np.unique(freqarr):
		if freqarr.count(j) % j != 0:
			print(-1)
			return
	num = 1
	dic = {}
	lex = []
	for i in freqarr:
		if i not in dic:
			dic[i] = (num, i - 1)
			num += 1
		elif dic[i][1] != 0:
			(num_, i_) = dic[i]
			dic[i] = (num_, i_ - 1)
		else:
			dic[i] = (num, i - 1)
			num += 1
		print(dic[i][0], end=' ')
	print()

def main():
	for i in range(inp()):
		lent = inp()
		lexsmall(lis())
main()


t = int(input())
for _ in range(t):
	n = int(input())
	B = list(map(int, input().split()))
	Bdict = {}
	for i in B:
		if i in Bdict:
			Bdict[i] += 1
		else:
			Bdict[i] = 1
	flag = 0
	for i in Bdict:
		if Bdict[i] % i != 0:
			flag = 1
	if flag == 1:
		print(-1)
	else:
		dictcount = {}
		dictassign = {}
		A = []
		j = 1
		for i in B:
			if i in dictcount:
				A.append(dictassign[i])
				dictcount[i] += 1
				if dictcount[i] == i:
					del dictcount[i]
			else:
				dictcount[i] = 1
				dictassign[i] = j
				A.append(j)
				if dictcount[i] == i:
					del dictcount[i]
				j = j + 1
		print(*A)


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if b[i] not in d:
			d[b[i]] = 1
		else:
			d[b[i]] += 1
	nums = 0
	for i in d:
		nums += d[i] / i
	if nums % 1 != 0:
		print(-1)
		continue
	else:
		nums = int(nums)
	ans = [0 for i in range(len(b))]
	num = 0
	d1 = {}
	d2 = {}
	for i in range(len(b)):
		if b[i] not in d1:
			num += 1
			d1[b[i]] = num
			d2[num] = 1
			ans[i] = num
		elif d2[d1[b[i]]] % b[i] != 0:
			ans[i] = d1[b[i]]
			d2[d1[b[i]]] += 1
		else:
			num += 1
			d1[b[i]] = num
			d2[num] = 1
			ans[i] = d1[b[i]]
	for i in ans:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	a = list()
	ref = dict()
	j = 1
	for i in b:
		if i == 1:
			a.append(j)
			j += 1
		else:
			if i not in ref.keys():
				ref[i] = [j, i]
				j += 1
			a.append(ref[i][0])
			ref[i][1] -= 1
			if not ref[i][1]:
				ref.pop(i)
	if ref:
		print(-1)
	else:
		print(*a)


t = int(input())
for i in range(t):
	x = int(input())
	flag = 0
	list1 = list(map(int, input().split()))
	dict1 = {}
	num = []
	ans = []
	for j in range(len(list1)):
		num.append(j + 1)
		if list1[j] not in dict1:
			dict1[list1[j]] = 1
		else:
			dict1[list1[j]] += 1
	for k in dict1.keys():
		if dict1[k] % k != 0:
			flag = -1
			break
	if flag != -1:
		q = 0
		dict3 = {}
		dict2 = {}
		x = []
		for r in range(len(list1)):
			x = dict2.keys()
			if list1[r] not in x:
				dict3[list1[r]] = num[q]
				dict2[list1[r]] = 1
				ans.append(num[q])
				q += 1
				if list1[r] == 1:
					del dict3[list1[r]]
					del dict2[list1[r]]
			elif list1[r] > dict2[list1[r]]:
				ans.append(dict3[list1[r]])
				dict2[list1[r]] += 1
				if dict2[list1[r]] == list1[r]:
					del dict3[list1[r]]
					del dict2[list1[r]]
		print(*ans)
	else:
		print('-1')


for i in range(0, int(input())):
	n = int(input())
	a = list(map(int, list(input().split())))
	d = {}
	ans = []
	count = 1
	for j in range(0, n):
		if a[j] in d.keys():
			ans.append(d[a[j]][0])
		else:
			d[a[j]] = [[count, a[j]]]
			count += 1
			ans.append(d[a[j]][0])
		d[a[j]][0][1] -= 1
		if d[a[j]][0][1] == 0:
			del d[a[j]]
	if len(d) != 0:
		print(-1)
	else:
		for j in range(n):
			print(ans[j][0], ' ', end='')
		print('\n')


import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache
import bisect
import heapq
import sys
input = lambda : sys.stdin.readline().strip()

class SegmentTree:

	def __init__(self, arr, func=lambda x, y: x + y, defaultvalue=0):
		self.n = len(arr)
		self.segmentTree = [0] * self.n + arr
		self.func = func
		self.defaultvalue = defaultvalue
		self.buildSegmentTree(arr)

	def buildSegmentTree(self, arr):
		for i in range(self.n - 1, 0, -1):
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

	def query(self, l, r):
		l += self.n
		r += self.n
		res = self.defaultvalue
		while l < r:
			if l & 1:
				res = self.func(res, self.segmentTree[l])
				l += 1
			l >>= 1
			if r & 1:
				r -= 1
				res = self.func(res, self.segmentTree[r])
			r >>= 1
		return res

	def update(self, i, value):
		i += self.n
		self.segmentTree[i] = value
		while i > 1:
			i >>= 1
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	c = Counter()
	mapp = {}
	ans = []
	last = 0
	for i in range(n):
		if c[arr[i]] == 0:
			last += 1
			mapp[arr[i]] = last
			c[arr[i]] = arr[i] - 1
			ans.append(last)
		else:
			c[arr[i]] -= 1
			ans.append(mapp[arr[i]])
	for i in c:
		if c[i] != 0:
			print(-1)
			return
	print(*ans)
for t in range(int(input())):
	solve()


T = int(input())
while T:
	T -= 1
	n = int(input())
	b = list(map(int, input().split()))
	d = {b[0]: [1]}
	numsl = [0, b[0] - 1]
	if not numsl[1]:
		del d[b[0]][0]
	ans = [1]
	num = 2
	if n == 1:
		print(1)
	else:
		for i in b[1:]:
			if i not in d or not d[i]:
				if i - 1:
					d[i] = [num]
				ans.append(num)
				num += 1
				numsl.append(i - 1)
			else:
				ans.append(d[i][0])
				numsl[d[i][0]] -= 1
				if not numsl[d[i][0]]:
					del d[i][0]
		if sum(numsl):
			print(-1)
		else:
			print(*ans)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = []
	d = {}
	c = 0
	f = False
	cnt = Counter(arr)
	for j in range(n):
		i = arr[j]
		if i in d:
			if cnt[i] % i == 0:
				c += 1
				d[i] = c
				ans.append(c)
			else:
				ans.append(d[i])
			cnt[i] -= 1
		elif cnt[i] % i == 0:
			c += 1
			d[i] = c
			cnt[i] = -1
			ans.append(c)
		else:
			f = True
			break
	if f == True:
		print(-1)
	else:
		print(*ans)


for _ in range(int(input())):
	n = int(input())
	nl = [int(x) for x in input().split()]
	dic = {}
	for i in nl:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
	flag = 0
	for i in nl:
		if dic[i] % i != 0:
			flag = 1
			break
	if flag:
		print(-1)
	else:
		aa = {}
		bc = {}
		j = 1
		arr = []
		for i in nl:
			if i in aa:
				arr += [bc[i]]
				aa[i] += 1
				if aa[i] == i:
					del aa[i]
			else:
				aa[i] = 1
				bc[i] = j
				arr += [j]
				if aa[i] == i:
					del aa[i]
				j += 1
		for i in range(n):
			print(arr[i], end=' ')
		print()


import collections
t = int(input())
for i in range(0, t):
	n = int(input())
	l = list(map(int, input().split()))
	dic = {}
	dic1 = {}
	frequency = collections.Counter(l)
	dic0 = dict(frequency)
	flag = 0
	for keys in dic0.keys():
		if dic0[keys] % keys != 0:
			flag = 1
			break
	j = 0
	if flag == 0:
		for i in l:
			if i not in dic.keys():
				j = j + 1
				dic[i] = j
				dic1[i] = i - 1
				print(j, end=' ')
			elif dic1[i] > 0:
				dic1[i] = dic1[i] - 1
				print(dic[i], end=' ')
			else:
				j = j + 1
				dic[i] = j
				dic1[i] = i - 1
				print(dic[i], end=' ')
		print()
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	elem = {}
	cnt = {}
	num = 1
	ans = [0 for i in range(n)]
	for i in range(n):
		if a[i] not in elem:
			elem[a[i]] = num
			cnt[num] = 1
			ans[i] = num
			num += 1
		else:
			e = elem[a[i]]
			if cnt[e] % a[i] != 0:
				ans[i] = e
				cnt[e] += 1
			else:
				ans[i] = num
				elem[a[i]] = num
				cnt[num] = 1
				num += 1
	temp = {}
	for e in ans:
		temp[e] = temp.get(e, 0) + 1
	f = 0
	for i in range(n):
		if a[i] != temp[ans[i]]:
			f = 1
			break
	if f == 0:
		print(*ans)
	else:
		print(-1)


def Solve(freq, n):
	(d, ans) = ({}, [])
	(next_element, size) = (1, 0)
	for i in range(n):
		if freq[i] == 1:
			size += 1
			ans.append(next_element)
			next_element += 1
		elif freq[i] not in d:
			size += freq[i]
			d[freq[i]] = [1, next_element]
			ans.append(next_element)
			next_element += 1
		else:
			value = d[freq[i]][1]
			ans.append(value)
			d[freq[i]][0] += 1
			if d[freq[i]][0] >= freq[i]:
				del d[freq[i]]
	if size > n:
		return [-1]
	else:
		return ans
for _ in range(int(input())):
	n = int(input())
	freq = list(map(int, input().split()))
	print(*Solve(freq, n))


from collections import defaultdict, Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	flag = 0
	for i in c:
		if c[i] % i != 0:
			flag = 1
			break
	if flag:
		print(-1)
		continue
	d = defaultdict(lambda : [0, 0])
	t = 0
	ans = []
	for i in a:
		if i in d and d[i][1] == i:
			t += 1
			d[i] = [t, 0]
		if i not in d:
			t += 1
			ans.append(t)
			d[i][0] = t
		else:
			ans.append(d[i][0])
		d[i][1] += 1
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	(d, ans, cnt, impossible) = (dict(), [], 1, False)
	for i in range(n):
		if d.get(b[i], [0, 0])[1] == 0:
			d[b[i]] = [cnt, b[i] - 1]
			cnt += 1
		else:
			d[b[i]][1] -= 1
		ans.append(str(d[b[i]][0]))
	for k in d.keys():
		if d[k][1] > 0:
			impossible = True
			break
	print(' '.join(ans) if not impossible else -1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = set(a)
	b = dict.fromkeys(b, 0)
	for i in a:
		b[i] += 1
	res = True
	for i in b:
		if b[i] % i != 0:
			print(-1)
			res = False
			break
	if res == True:
		j = 1
		l = [0] * n
		dic = {}
		for i in range(n):
			if b[a[i]] % a[i] == 0:
				dic[a[i]] = j
				j += 1
			b[a[i]] -= 1
			l[i] = dic[a[i]]
		print(*l)


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	a = [-1 for i in range(n)]
	dic = {}
	for i in range(n):
		if b[i] in dic:
			dic[b[i]].append(i)
		else:
			dic[b[i]] = [i]
	yes = 1
	for i in dic.keys():
		if len(dic[i]) % i:
			yes = 0
			break
	if yes == 0:
		print('-1')
		continue
	num = 1
	for i in range(n):
		if a[i] != -1:
			continue
		for j in range(b[i]):
			a[dic[b[i]][0]] = str(num)
			dic[b[i]].pop(0)
		num += 1
	print(' '.join(a))


NumTests = int(input())
for test in range(NumTests):
	N = int(input())
	B = list(map(int, input().split(' ')))
	freqdict = {}
	for b in B:
		if b in freqdict.keys():
			freqdict[b] += 1
		else:
			freqdict[b] = 1
	flag = 'Pass'
	for k in freqdict:
		if freqdict[k] % k != 0:
			flag = 'Fail'
			break
	if flag == 'Fail':
		print(-1)
		continue
	Result = []
	nextfree = 1
	trackerdict1 = {}
	trackerdict2 = {}
	for b in B:
		if b in trackerdict1.keys():
			Result.append(trackerdict1[b])
			trackerdict2[b] -= 1
		else:
			trackerdict1[b] = nextfree
			trackerdict2[b] = b - 1
			Result.append(nextfree)
			nextfree += 1
		if trackerdict2[b] == 0:
			del trackerdict2[b]
			del trackerdict1[b]
	for r in Result:
		print(r, end=' ')
	print()


for _ in range(int(input())):
	_ = input()
	b = list(map(int, input().split()))
	updated = set()
	num = 1
	for i in range(len(b)):
		if i in updated:
			continue
		bi = b[i]
		b[i] = num
		updated.add(i)
		changed = 1
		for j in range(i + 1, len(b)):
			if j in updated:
				continue
			if changed == bi:
				break
			if b[j] == bi:
				b[j] = num
				updated.add(j)
				changed += 1
		if changed != bi:
			print(-1)
			break
		num += 1
	else:
		print(' '.join([str(i) for i in b]))


def minarr(l1):
	l3 = []
	l2 = set(l1)
	from collections import defaultdict
	d1 = defaultdict(list)
	t = 0
	for x in l2:
		d1[x] = []
	for x in l1:
		if len(d1[x]) != x:
			if len(d1[x]) != 0:
				l3.append(d1[x][0])
				d1[x].append(d1[x][0])
			else:
				t += 1
				d1[x].append(t)
				l3.append(t)
		else:
			t += 1
			d1[x] = []
			d1[x].append(t)
			l3.append(t)
	return l3
for q in range(int(input())):
	n = int(input())
	l1 = [int(x) for x in input().split()]
	l2 = set(l1)
	s = 0
	for x in l2:
		if l1.count(x) % x != 0:
			s = 1
			break
	if s == 1:
		print(-1)
	else:
		print(*minarr(l1))


for _ in range(int(input())):
	n = int(input())
	B = list(map(int, input().split()))
	B_arr = {}
	for i in B:
		if i in B_arr:
			B_arr[i] += 1
		else:
			B_arr[i] = 1
	count = 0
	for i in B_arr:
		if B_arr[i] % i != 0:
			count = 1
	if count == 1:
		print(-1)
	else:
		count_arr = {}
		assign_arr = {}
		A = []
		j = 1
		for i in B:
			if i in count_arr:
				A.append(assign_arr[i])
				count_arr[i] += 1
				if count_arr[i] == i:
					del count_arr[i]
			else:
				count_arr[i] = 1
				assign_arr[i] = j
				A.append(j)
				if count_arr[i] == i:
					del count_arr[i]
				j = j + 1
		print(*A)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = dict(Counter(l))
	for i in d.keys():
		if d[i] % i != 0:
			print(-1)
			break
	else:
		d = {}
		c = 0
		for i in l:
			if i not in d.keys():
				c += 1
				d[i] = [[c], 1]
			elif d[i][1] % i == 0:
				c += 1
				d[i][0].append(c)
				d[i][1] += 1
			else:
				d[i][1] += 1
		d1 = {}
		for i in l:
			if i not in d1.keys():
				print(d[i][0][0], end=' ')
				d1[i] = 1
			else:
				print(d[i][0][d1[i] // i], end=' ')
				d1[i] += 1
		print()


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	B = inlt()
	an = []
	mx = 10 ** 5
	x = 1
	dic = {B[0]: [x] * B[0]}
	mx -= B[0]
	for b in B:
		if b not in dic or not dic[b]:
			x += 1
			dic[b] = [x] * b
			mx -= b
			if mx < 0:
				break
		an.append(dic[b].pop())
	for x in dic:
		if dic[x] or mx < 0:
			an = [-1]
			break
	ans.append(an)
outpltlt(ans)


for _ in range(int(input())):
	n = int(input())
	freq = list(map(int, input().split()))
	x = 1
	for i in set(freq):
		if freq.count(i) % i != 0:
			print(-1)
			break
	else:
		res = [0] * n
		dic = {}
		check = {}
		for i in range(n):
			p = freq[i]
			if p in check and check[p] == p:
				check.pop(p)
				dic.pop(p)
			if p == 1:
				res[i] = x
				x = x + 1
			elif p in dic:
				res[i] = dic[p]
				check[p] += 1
			elif p not in dic:
				dic[p] = x
				res[i] = x
				check[p] = 1
				x += 1
		print(*res)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	for i in range(len(arr)):
		if arr[i] not in d:
			d[arr[i]] = [i]
		else:
			d[arr[i]].append(i)
	s = 0
	for i in d:
		if len(d[i]) % i != 0:
			s = -1
			break
		s += len(d[i])
	if s != n:
		print(-1)
	else:
		l = [0] * n
		j = 1
		for i in range(len(arr)):
			if l[i] == 0:
				x = d[arr[i]]
				y = arr[i]
				for k in x:
					if y > 0:
						l[k] = j
						y -= 1
					else:
						break
				del x[0:arr[i]]
				j += 1
			else:
				continue
		[print(i, end=' ') for i in l]
		print()
	t -= 1


from collections import defaultdict, Counter
from os import path
import sys
from collections import defaultdict
import math

def int_inp():
	return int(input())

def mul_inp():
	return map(int, input().split())

def arr_inp():
	return list(map(int, input().split()))

def is_prime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return False

def factors(x):
	result = []
	i = 1
	while i * i <= x:
		if x % i == 0:
			result.append(i)
			if x // i != i:
				result.append(x // i)
		i += 1
	return sorted(result)

def factors1(x):
	i = 2
	while i * i <= x:
		if x % i == 0:
			return i
		i += 1
	return x

def prime_factors(x):
	result = []
	i = 1
	while i * i <= x:
		if x % i == 0:
			result.append(i)
		i += 1
	return sorted(result)

def solution():
	n = int_inp()
	arr = arr_inp()
	m1 = Counter(arr)
	s = 0
	for i in m1.keys():
		if m1[i] % i != 0:
			print(-1)
			return
	m2 = defaultdict(int)
	m3 = defaultdict(int)
	start = 0
	ans = [0] * n
	for i in range(n):
		if m2[arr[i]]:
			ans[i] = m3[arr[i]]
			m2[arr[i]] -= 1
		else:
			start += 1
			m3[arr[i]] = start
			m2[arr[i]] = arr[i]
			ans[i] = m3[arr[i]]
			m2[arr[i]] -= 1
	print(*ans)
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int_inp()):
	x = solution()


testcases = int(input())
for i in range(testcases):
	n = int(input())
	data = list(map(int, input().split()))
	flag = 0
	check = {}
	for i in data:
		if i in check:
			check[i] += 1
		else:
			check[i] = 1
	for i in check:
		if check[i] % i != 0:
			flag = 1
	if flag == 1:
		print(-1)
	else:
		datacount = {}
		dataassign = {}
		j = 1
		val = []
		for i in data:
			if i not in datacount:
				datacount[i] = 1
				dataassign[i] = j
				val.append(j)
				if datacount[i] == i:
					del datacount[i]
				j = j + 1
			else:
				datacount[i] += 1
				val.append(dataassign[i])
				if datacount[i] == i:
					del datacount[i]
		print(*val)


import numpy as np
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	c = 1
	a = [None] * n
	i = 0
	flag = False
	for i in set(b):
		if b.count(i) % i != 0:
			flag = True
			break
	if flag:
		print(-1)
	else:
		for i in range(n):
			if b[i] == 0:
				continue
			else:
				rep = b[i]
				cont = b[i]
				for j in range(i, n):
					if cont <= 0:
						break
					if b[j] == rep:
						a[j] = c
						cont -= 1
						b[j] = 0
				c += 1
		print(*a)


from collections import defaultdict
for _ in range(int(input())):
	c = int(input())
	arr = [int(i) for i in input().split()]
	a = defaultdict(int)
	b = {}
	ans = []
	cnt = 0
	for i in range(c):
		if a[arr[i]]:
			ans.append(b[arr[i]])
			a[arr[i]] -= 1
		else:
			cnt += 1
			a[arr[i]] = arr[i] - 1
			b[arr[i]] = cnt
			ans.append(cnt)
		if not a[arr[i]]:
			del a[arr[i]]
	if a:
		ans = [-1]
	print(*ans)


for i in range(int(input())):
	n = int(input())
	B = [int(j) for j in input().split()]
	u = {}
	k = 1
	for j in range(n):
		if B[j] not in u:
			u[B[j]] = [1, k]
			k += 1
		else:
			if u[B[j]][0] % B[j] == 0:
				u[B[j]].append(k)
				k += 1
			u[B[j]][0] += 1
	b = True
	for j in u:
		if u[j][0] % j != 0:
			b = False
			break
	if b:
		k = 1
		for j in B:
			print(u[j][1], end=' ')
			u[j][0] -= 1
			if u[j][0] % j == 0:
				u[j].pop(1)
		print()
	else:
		print(-1)


for _ in range(int(input())):
	dic = {}
	n = int(input())
	ls = list(map(int, input().split()))
	arr = [0] * (n + 1)
	ans = []
	dic = {}
	count = 0
	num = 0
	for i in range(n):
		if ls[i] > n:
			count = n + 1
			break
		if arr[ls[i]] == 0:
			num += 1
			dic[ls[i]] = num
			arr[ls[i]] = ls[i] - 1
			count += ls[i]
			ans.append(num)
		else:
			ans.append(dic[ls[i]])
			arr[ls[i]] -= 1
	if count != n:
		print(-1)
	else:
		print(*ans)


t = int(input())
for _ in range(t):
	n = int(input())
	B = list(map(int, input().split()))
	countRecord = {}
	for freq in B:
		countRecord[freq] = countRecord.get(freq, 0) + 1
	flag = False
	for (key, value) in countRecord.items():
		if value % key != 0:
			flag = True
			print(-1)
			break
	if flag:
		continue
	record = {}
	A = [0] * n
	for i in range(n):
		if B[i] in record:
			record[B[i]].append(i)
		else:
			record[B[i]] = [i]
	count = 1
	visited = set()
	for i in range(n):
		if i not in visited:
			c2 = 0
			flag = False
			while record[B[i]] and c2 != B[i]:
				flag = True
				idx = record[B[i]].pop(0)
				visited.add(idx)
				A[idx] = count
				c2 += 1
			if flag:
				count += 1
	print(*A)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	a = []
	d = defaultdict(lambda : [0, 0])
	f = 1
	for i in range(n):
		v = b[i]
		if d[v][0] == 0:
			d[v][0] = f
			a.append(f)
			f += 1
			d[v][1] += 1
			if d[v][1] >= v:
				d[v][1] = 0
				d[v][0] = 0
		else:
			d[v][1] += 1
			a.append(d[v][0])
			if d[v][1] >= v:
				d[v][1] = 0
				d[v][0] = 0
	poss = True
	for i in d:
		if d[i][0] != 0:
			poss = False
			break
	if not poss:
		print(-1)
	else:
		for i in a:
			print(i, end=' ')
		print()


tpy = int(input())
for i in range(tpy):
	n = int(input())
	b = list(map(int, input().split()))
	a = []
	c = {}
	d = 1
	for j in range(n):
		if b[j] not in c.keys():
			c[b[j]] = [d, b[j] - 1]
			d = d + 1
			a.append(c[b[j]][0])
		else:
			a.append(c.get(b[j])[0])
			l = c.get(b[j])
			l[1] = l[1] - 1
			c[b[j]] = l
		if c.get(b[j])[1] < 1:
			del c[b[j]]
	if bool(c) == True:
		a.clear()
		a.append(-1)
	print(' '.join(map(str, a)))


def solve():
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		if i not in d.keys():
			d[i] = 0
		d[i] += 1
	for i in d.keys():
		if d[i] % i != 0:
			print(-1)
			return
	x = {}
	y = {}
	z = 1
	for i in l:
		if i not in x.keys() or i not in y.keys() or y[i] == 0:
			x[i] = z
			z += 1
			y[i] = i
		print(x[i], end=' ')
		y[i] -= 1
	print()
for _ in range(int(input())):
	solve()


testcases = int(input())
for eachcase in range(testcases):
	length = int(input())
	array = list(map(int, input().split()))
	value = 0
	hashmapA = {}
	hashmapB = {}
	finalarray = []
	for nums in array:
		hashmapA[nums] = 1 + hashmapA.get(nums, 0)
	for nums in array:
		if hashmapA[nums] % nums == 0:
			value += 1
			hashmapB[nums] = value
			finalarray.append(value)
			hashmapA[nums] -= 1
		elif nums in hashmapB:
			finalarray.append(hashmapB[nums])
			hashmapA[nums] -= 1
		else:
			finalarray.append(-1)
			break
	if finalarray[-1] == -1:
		print(-1)
	else:
		print(*finalarray)


import sys
R = lambda : map(int, next(sys.stdin).split())
T = int(input())
for i in range(T):
	length = int(input())
	B = list(R())
	maxB = max(B)
	valid = []
	numberFrequency = []
	for i in range(maxB + 1):
		numberFrequency.append(0)
	numberCount = numberFrequency.copy()
	unique = 1
	for i in range(length):
		if numberFrequency[B[i]] == 0:
			numberFrequency[B[i]] = unique
			numberCount[B[i]] = B[i]
			unique += 1
		numberCount[B[i]] -= 1
		valid.append(str(numberFrequency[B[i]]))
		if numberCount[B[i]] == 0:
			numberFrequency[B[i]] = 0
	empty = 1
	for i in range(len(numberFrequency)):
		if numberFrequency[i] != 0:
			empty = 0
	if empty == 1:
		print(' '.join(valid))
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	d = {}
	for i in ar:
		d[i] = d.get(i, 0) + 1
	flag = 0
	for i in d:
		if d[i] % i != 0:
			flag = 1
	if flag == 1:
		print(-1)
	else:
		a = {}
		b = {}
		l = []
		k = 1
		for i in ar:
			if i in a:
				l.append(b[i])
				a[i] += 1
				if a[i] == i:
					del a[i]
			else:
				a[i] = 1
				b[i] = k
				l.append(k)
				if a[i] == i:
					del a[i]
				k += 1
		print(*l)


from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	res = []
	val = 1
	d = {}
	d2 = defaultdict(int)
	for ele in arr:
		d2[ele] += 1
		if ele not in d:
			(key, cnt) = (val, 0)
			val += 1
		else:
			(key, cnt) = d[ele]
		if cnt == ele:
			(key, cnt) = (val, 0)
			val += 1
		res.append(key)
		d[ele] = [key, cnt + 1]
	for key in d2:
		if d2[key] % key != 0:
			res = [-1]
	for ele in res:
		print(ele, end=' ')
	print()


T = int(input())
for t in range(0, T):
	L = int(input())
	B = list(map(int, input().split()))
	A = []
	EH = {}
	FH = {}
	a = 1
	for i in B:
		if i in EH:
			A.append(EH[i])
			FH[i] += 1
			if FH[i] == i:
				del EH[i]
				del FH[i]
			continue
		else:
			A.append(a)
			if i == 1:
				a += 1
				continue
			else:
				EH[i] = a
				FH[i] = 1
				a += 1
				continue
	if not EH:
		print(*A)
	else:
		print(-1)


def reconstruct_array(B):
	a = []
	using = {}
	j = 1
	k = 0
	s = 0
	for i in B:
		if i in using:
			if using[i][0][1] == 0:
				using[i] = [[j, i]]
				j += 1
				s += i
			a.append(using[i][0][0])
			using[i][0][1] -= 1
		else:
			using[i] = [[j, i]]
			s += i
			j += 1
			a.append(using[i][0][0])
			using[i][0][1] -= 1
	if s > len(B):
		return [-1]
	return a
for _ in range(int(input())):
	n = int(input())
	B = list(map(int, input().split()))
	print(*reconstruct_array(B))


from collections import Counter
import itertools
op = int(input())
for i in range(op):
	n = int(input())
	a = list(map(int, input().split()))
	w = Counter(a)
	d = {}
	e = 1
	for i in w:
		if i > len(a):
			e = 0
			print('-1')
			break
		if w[i] % i != 0:
			e = 0
			print('-1')
			break
	if e:
		h = {}
		for i in range(len(a)):
			if a[i] in d:
				d[a[i]] += 1
			else:
				d[a[i]] = 1
		for i in range(len(a)):
			if a[i] in h:
				pass
			else:
				h[a[i]] = 0
		curr = 1
		new = 0
		for i in range(len(a)):
			if h[a[i]] == 0:
				print(curr, end=' ')
				d[a[i]] -= 1
				h[a[i]] = curr
				curr += 1
			elif d[a[i]] % a[i] == 0:
				h[a[i]] = curr
				print(h[a[i]], end=' ')
				d[a[i]] -= 1
				curr += 1
			elif d[a[i]] % a[i] != 0:
				d[a[i]] -= 1
				print(h[a[i]], end=' ')
		print()


t = int(input())
for i in range(t):
	n = int(input())
	B = list(map(int, input().split()))
	bdict = {}
	for i in B:
		if i in bdict:
			bdict[i] += 1
		else:
			bdict[i] = 1
	flag = 0
	for i in bdict:
		if bdict[i] % i != 0:
			flag = 1
			break
	if flag == 1:
		print(-1)
	else:
		A = []
		cdict = {}
		adict = {}
		j = 1
		for i in B:
			if i in cdict:
				A.append(adict[i])
				cdict[i] += 1
				if cdict[i] == i:
					del cdict[i]
			else:
				cdict[i] = 1
				adict[i] = j
				A.append(j)
				if cdict[i] == i:
					del cdict[i]
				j += 1
		print(*A)


import collections
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	f = collections.Counter(b)
	pas = True
	for i in f:
		if f[i] % i != 0:
			pas = False
		f[i] = 0
	if pas == False:
		print(-1)
	else:
		g = f.copy()
		res = []
		c = 1
		for i in b:
			if f[i] != i:
				f[i] += 1
				if g[i] != 0:
					res.append(g[i])
				else:
					g[i] = c
					res.append(g[i])
					c += 1
			else:
				f[i] = 1
				g[i] = c
				res.append(g[i])
				c += 1
		print(*res)


import sys
from itertools import islice
for s in islice(sys.stdin, 2, None, 2):
	a = []
	d = {}
	i = 0
	for x in map(int, s.split()):
		if (y := d.get(x)) is None:
			y = d[x] = [(i := (i + 1)), x]
		a.append(y[0])
		y[1] -= 1
		if y[1] == 0:
			del d[x]
	print(*([-1] if d else a))


import collections
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	freq = collections.Counter(b)
	curval = {}
	nxt = 1
	a = [-1] * n
	for i in range(n):
		if freq[b[i]] % b[i] == 0:
			curval[b[i]] = nxt
			nxt += 1
		if b[i] not in curval:
			break
		freq[b[i]] -= 1
		a[i] = curval[b[i]]
	if min(a) == -1:
		print(-1)
	else:
		print(*a)


from collections import defaultdict, Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	val = {}
	t = 1
	ans = [0] * n
	for i in range(n):
		if c[a[i]] % a[i] == 0:
			val[a[i]] = t
			t += 1
		if a[i] not in val:
			break
		c[a[i]] -= 1
		ans[i] = val[a[i]]
	if min(ans) == 0:
		print(-1)
	else:
		print(*ans)


def abc():
	n = int(input())
	b = list(map(int, input().split()))
	freq = {}
	for i in b:
		if i not in freq.keys():
			freq[i] = 0
		freq[i] += 1
	for i in b:
		if freq[i] % i != 0:
			print('-1')
			return
	(m, f) = ({}, {})
	j = 1
	for i in b:
		if i not in m.keys() or i not in f.keys() or f[i] == 0:
			m[i] = j
			f[i] = i
			j += 1
		print(m[i], end=' ')
		f[i] -= 1
	print()
for _ in range(int(input())):
	abc()


def solve():
	flag = 0
	n = int(input())
	arr = list(map(int, input().split()))
	freq = dict()
	for i in arr:
		if i not in freq.keys():
			freq[i] = 0
		freq[i] += 1
	for i in freq.keys():
		if freq[i] % i != 0:
			print(-1)
			return
	m = {}
	f = {}
	j = 1
	for i in arr:
		if i not in m.keys() or i not in f.keys() or f[i] == 0:
			m[i] = j
			j += 1
			f[i] = i
		print(m[i], end=' ')
		f[i] -= 1
	print()
try:
	t = int(input())
	while t > 0:
		solve()
		t -= 1
except:
	pass


from collections import Counter

def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	N = int(input())
	arr = inparr()
	hm = Counter(arr)
	ok = True
	for i in hm:
		if hm[i] % i:
			ok = False
			break
	if sum(hm.keys()) > N or not ok:
		print(-1)
		continue
	d1 = Counter()
	dprev = 0
	res = ''
	for i in arr:
		if hm[i] % i == 0:
			dprev += 1
			d1[i] = dprev
		res += f'{d1[i]} '
		hm[i] -= 1
	print(res)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	d = {}
	count = 1
	s = set(l)
	for j in s:
		d[j] = [0, 0]
	for k in l:
		if d[k][1] == 0:
			d[k][1] = k
			d[k][0] = count
			count += 1
		if d[k][1] != 0:
			l1.append(d[k][0])
			d[k][1] -= 1
	for q in d.values():
		if q[1] != 0:
			print(-1)
			break
	else:
		for w in l1:
			print(w, end=' ')
		print()


import collections
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	freq = collections.Counter(a)
	vals = {}
	c = 1
	res = []
	for i in a:
		if freq[i] % i == 0:
			vals[i] = c
			c += 1
		if i not in vals:
			break
		res.append(vals[i])
		freq[i] -= 1
	if len(res) == n:
		print(*res)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0] * n
	d = {}
	for item in arr:
		if item in d:
			d[item] += 1
		else:
			d[item] = 1
	start = 1
	curr_val = {}
	for i in range(n):
		if d[arr[i]] % arr[i] == 0:
			curr_val[arr[i]] = start
			start += 1
		if arr[i] not in curr_val:
			break
		d[arr[i]] -= 1
		ans[i] = curr_val[arr[i]]
	if min(ans) == 0:
		print(-1)
	else:
		print(*ans)


from collections import Counter
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = Counter(l)
	l1 = []
	k = list(d.keys())
	v = list(d.values())
	for j in range(0, len(list(d.values()))):
		l1.append(v[j] % k[j])
	d1 = dict()
	for j in range(len(k)):
		d1[k[j]] = 0
	l2 = []
	for j in l:
		if d[j] % j == 0:
			d1[j] = max(list(d1.values())) + 1
		l2.append(d1[j])
		d[j] -= 1
	if max(l1) != 0:
		print('-1')
	else:
		for j in l2:
			print(j, end=' ')
		print()


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
import collections
for _ in range(ni()):
	n = ni()
	b = li()
	freq = collections.Counter(b)
	curval = {}
	nxt = 1
	a = [-1] * n
	for i in range(n):
		if freq[b[i]] % b[i] == 0:
			curval[b[i]] = nxt
			nxt += 1
		if b[i] not in curval:
			break
		freq[b[i]] -= 1
		a[i] = curval[b[i]]
	if min(a) == -1:
		print(-1)
	else:
		print(*a)


for hm in range(int(input())):
	a = int(input())
	b = list(map(int, input().strip().split(' ')))
	c = 0
	e = set(b)
	k = {}
	for hm in b:
		if hm in k:
			k[hm] += 1
		else:
			k[hm] = 1
	for hm in e:
		c += k[hm] // hm * hm
	if c != a:
		print(-1)
		continue
	m = 1
	n = {}
	v = set(b)
	for hm in range(a):
		if b[hm] in n and n[b[hm]][1] > 0:
			n[b[hm]][1] -= 1
			b[hm] = n[b[hm]][0]
		else:
			n[b[hm]] = [m, b[hm] - 1]
			b[hm] = m
			m += 1
	print(*b)