A class of students got bored wearing the same pair of shoes every day, so they decided to shuffle their shoes among themselves. In this problem, a pair of shoes is inseparable and is considered as a single object.

There are $n$ students in the class, and you are given an array $s$ in non-decreasing order, where $s_i$ is the shoe size of the $i$-th student. A shuffling of shoes is valid only if no student gets their own shoes and if every student gets shoes of size greater than or equal to their size.

You have to output a permutation $p$ of $\{1,2,\ldots,n\}$ denoting a valid shuffling of shoes, where the $i$-th student gets the shoes of the $p_i$-th student ($p_i \ne i$). And output $-1$ if a valid shuffling does not exist.

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\leq n\leq10^5$) — the number of students.

The second line of each test case contains $n$ integers $s_1, s_2,\ldots,s_n$ ($1\leq s_i\leq10^9$, and for all $1\le i<n$, $s_i\le s_{i+1}$) — the shoe sizes of the students.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, print the answer in a single line using the following format.

If a valid shuffling does not exist, print the number $-1$ as the answer.

If a valid shuffling exists, print $n$ space-separated integers — a permutation $p$ of $1,2,\ldots,n$ denoting a valid shuffling of shoes where the $i$-th student gets the shoes of the $p_i$-th student. If there are multiple answers, then print any of them.


-----Examples-----

Input
2
5
1 1 1 1 1
6
3 6 8 13 15 21
Output
5 1 2 3 4 
-1


-----Note-----

In the first test case, any permutation $p$ of $1,\ldots,n$ where $p_i\ne i$ would represent a valid shuffling since all students have equal shoe sizes, and thus anyone can wear anyone's shoes.

In the second test case, it can be shown that no valid shuffling is possible.

Difficulty: EASY
Tags: Greedy algorithms

Amortized analysis

Implementation

Constructive algorithms
Skill types: Amortized analysis

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	s = input().split()
	if n == 1:
		print(-1)
		continue
	exists = True
	flag = 0
	prev = s[0]
	perms = []
	for j in range(1, n):
		if s[j] == prev:
			perms.append(str(j + 1))
			continue
		if flag == j - 1:
			exists = False
			break
		perms.append(str(flag + 1))
		prev = s[j]
		flag = j
	if flag == n - 1:
		exists = False
	perms.append(str(flag + 1))
	if not exists:
		print(-1)
	else:
		print(' '.join(perms))


def solve():
	if n == 1:
		return -1
	ans = []
	first = 0
	for i in range(1, n):
		if arr[i] == arr[first]:
			ans.append(i + 1)
		else:
			if i == first + 1:
				return -1
			ans.append(first + 1)
			first = i
	ans.append(first + 1)
	if first + 1 == n:
		return -1
	else:
		ans = ' '.join(map(str, ans))
		return ans
T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = solve()
	print(ans)


def get():
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [str(i + 1) for i in range(n)]
	i = n - 1
	while i >= 0:
		c = 0
		j = i - 1
		while j >= 0 and arr[i] == arr[j]:
			c += 1
			(ans[j + 1], ans[j]) = (ans[j], ans[j + 1])
			j -= 1
		if c == 0:
			return -1
		i = j
	return ' '.join(ans)
for _ in range(int(input())):
	print(get())


t = int(input())
for tt in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	if n == 1:
		print(-1)
		continue
	current_size = s[0]
	batch = [1]
	solution = []
	for i in range(1, n):
		if s[i] == current_size:
			batch.append(i + 1)
		else:
			if len(batch) < 2:
				break
			solution.append(batch[-1])
			solution.extend(batch[:-1])
			batch = [i + 1]
			current_size = s[i]
	if len(batch) > 1:
		solution.append(batch[-1])
		solution.extend(batch[:-1])
	else:
		print(-1)
		continue
	print(' '.join(map(str, solution)))


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	if n == 1:
		print(-1)
		continue
	prev = s[0]
	perms = []
	found = True
	curr = 0
	for i in range(1, n):
		if s[i] == prev:
			perms.append(str(i + 1))
			continue
		if i - 1 == curr:
			found = False
			break
		perms.append(str(curr + 1))
		prev = s[i]
		curr = i
	if curr == n - 1:
		found = False
	perms.append(str(curr + 1))
	if not found:
		print(-1)
	else:
		print(' '.join(perms))


def solve(arr):
	ans = []
	arr.append(-1)
	(prev, cnt) = (arr[0], 0)
	for (i, num) in enumerate(arr):
		if num == prev:
			cnt += 1
		else:
			if cnt == 1:
				return -1
			ans.append(i)
			for j in range(i - cnt + 1, i):
				ans.append(j)
			prev = num
			cnt = 1
	return ' '.join(list(map(str, ans)))

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		print(solve(list(map(int, input().split()))))
main()


def ss(n, l):
	if n == 1:
		return -1
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	ans = []
	x = 1
	for i in d:
		if d[i] == 1:
			return -1
		for k in range(x + 1, d[i] + x):
			ans.append(k)
		ans.append(x)
		x = ans[-2] + 1
	for i in range(len(ans)):
		ans[i] = str(ans[i])
	return ' '.join(ans)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(ss(n, l))


def task(n, a):
	cache = dict()
	for i in a:
		if i in cache:
			cache[i] += 1
		else:
			cache[i] = 1
	results = []
	current = 0
	for (key, value) in cache.items():
		if value == 1:
			print(-1)
			return
		else:
			results.append(current + value)
			for i in range(current + 1, current + value):
				results.append(i)
			current += value
	print(' '.join((str(result) for result in results)))
t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	task(n, a)


from collections import Counter
from itertools import groupby
for _ in range(int(input())):
	n = int(input())
	o = 0
	e = 0
	s = input().split()
	c = Counter(s)
	if min(c.values()) < 2:
		print(-1)
		continue
	cs = 0
	x = list(range(1, len(s) + 1))
	ans = []
	for (k, g) in groupby(s):
		cl = len(list(g))
		ce = cs + cl
		ans.append(x[ce - 1])
		ans.extend(x[cs:ce - 1])
		cs = ce
	print(' '.join(map(str, ans)))


t = int(input())
for testcase in range(t):
	n = int(input())
	s = [int(x) for x in input().split()]
	result = []
	if n == 1:
		print(-1)
	else:
		valid = True
		i = 0
		while i < n:
			j = i + 1
			while j < n and s[j] == s[i]:
				result.append(j + 1)
				j += 1
			if j - i == 1:
				valid = False
				break
			result.append(i + 1)
			i = j
		if valid:
			result = [str(x) for x in result]
			print(' '.join(result))
		else:
			print(-1)


def f(n, arr):
	ans = []
	i = 0
	while i < n:
		cur = i + 1
		I = i
		while i < n and arr[I] == arr[i]:
			i += 1
		filler = list(range(i, I, -1))
		m = len(filler)
		if m == 1:
			return [-1]
		mid = m // 2
		if m % 2 == 1:
			(filler[mid], filler[mid - 1]) = (filler[mid - 1], filler[mid])
		ans += filler
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(' '.join(map(str, f(n, arr))))


for _ in range(int(input())):
	n = int(input())
	x = input().split()
	if len(set(x)) == n:
		print(-1)
		continue
	y = list(map(str, range(1, n + 1)))
	p = x[0]
	q = 1
	s = ''
	for (i, a) in enumerate(x[1:]):
		if p == a:
			q += 1
		else:
			if q == 1:
				print(-1)
				break
			s += str(i + 1) + ' ' + ' '.join(y[i - q + 1:i]) + ' '
			p = a
			q = 1
	else:
		i += 1
		if q > 1:
			s += str(i + 1) + ' ' + ' '.join(y[i - q + 1:i])
		elif q == 1:
			print(-1)
			continue
		print(s)


import sys
input = sys.stdin.readline

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

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
tests = inp()
for j in range(0, tests):
	n = inp()
	x = inlt()
	y = [*range(0, n)]
	val = 0
	idx_last = 0
	idx_zero = 0
	count = 0
	if n == 1:
		print(-1)
	else:
		for i in range(0, n):
			if val != x[i]:
				val = x[i]
				idx_last = i
				y[idx_zero] = y[idx_last]
				idx_zero = i
				if count == 1:
					y = -1
					break
				count = 1
			elif val == x[i]:
				count += 1
			if val == x[i] and i + 1 == n:
				y[idx_zero] = n
		if count == 1:
			y = -1
		if isinstance(y, list):
			print(' '.join(map(str, y)))
		else:
			print(y)


t = int(input())
ans = list()
for i in range(0, t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if len(arr) == 1 or arr[-1] != arr[-2]:
		ans.append(-1)
		continue
	v = arr[0]
	count = 1
	for i in range(1, len(arr)):
		if arr[i] == v:
			count += 1
		elif count < 2:
			ans.append(-1)
			break
		else:
			count = 1
			v = arr[i]
	else:
		s = ''
		v = arr[0]
		j = 1
		for i in range(1, len(arr)):
			if arr[i] != v:
				s += f'{j} '
				v = arr[i]
				j = i + 1
			else:
				s += f'{i + 1} '
		s += f'{j} '
		ans.append(s)
for s in ans:
	print(s)


def solve(n, nums):
	(i, last) = (0, 0)
	sol = []
	while i < n:
		last = nums[i]
		j = i + 1
		while j < n and nums[j] == last:
			j += 1
		if j - i == 1:
			return [-1]
		else:
			for k in range(i + 1, j):
				sol.append(k + 1)
			sol.append(i + 1)
		i = j
	return sol
t = int(input())
for c in range(t):
	n = int(input())
	nums = [int(x) for x in input().split()]
	sol = solve(n, nums)
	print(' '.join([str(s) for s in sol]))


def perm(size):
	count = {}
	for i in size:
		count[i] = count.get(i, 0) + 1
	if 1 in count.values():
		ans = '-1'
	else:
		ans = ''
		curr = 0
		for i in range(1, len(size)):
			if size[i] == size[curr]:
				ans += str(i + 1) + ' '
				continue
			else:
				ans += str(curr + 1) + ' '
				curr = i
		ans += str(curr + 1)
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	size = list(map(int, input().split()))
	print(perm(size))


def f(n, a):
	q = ''
	w = a[0]
	e = 1
	for i in range(1, n):
		if a[i] == w:
			e += 1
		elif e > 1:
			p = str(i) + ' ' + ' '.join(map(str, list(range(i - e + 1, i))))
			q += p + ' '
			w = a[i]
			e = 1
		else:
			return -1
	if e > 1:
		p = str(i + 1) + ' ' + ' '.join(map(str, list(range(i - e + 2, i + 1))))
		q += p + ' '
		return q
	else:
		return -1
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(f(n, a))


from collections import defaultdict

def shoe_shuffling(ar):
	n = len(ar)
	d = defaultdict(list)
	for (ix, v) in enumerate(ar):
		d[v].append(str(ix + 1))
	ar_shuffled = []
	for (v, ixs) in d.items():
		if len(ixs) == 1:
			print(-1)
			return
		else:
			ar_shuffled.extend(ixs[-1:] + ixs[:-1])
	print(' '.join(ar_shuffled))
t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split(' ')))
	shoe_shuffling(ar)


for _ in range(int(input())):
	input()
	nums = list(map(int, input().split()))
	answer = []
	s = []
	val = -1
	minus_flg = False
	if len(nums) < 2:
		print(-1)
		continue
	for (i, num) in enumerate(nums):
		if num == val:
			s.append(i + 1)
		else:
			if len(s) == 1:
				print(-1)
				minus_flg = True
				break
			if len(s) > 0:
				answer.append(s[-1])
			for j in range(len(s) - 1):
				answer.append(s[j])
			val = num
			s.clear()
			s.append(i + 1)
	if minus_flg:
		continue
	if len(s) == 1:
		print(-1)
		continue
	answer.append(s[-1])
	for i in range(len(s) - 1):
		answer.append(s[i])
	print(' '.join(list(map(str, answer))))


def solution(n, shoes):
	dicto = {}
	for (i, s) in enumerate(shoes):
		if s in dicto:
			dicto[s].append(i)
		else:
			dicto[s] = [i]
	for s in dicto.keys():
		if len(dicto[s]) == 1:
			print('-1')
			return
	res = [-1] * n
	for s in dicto.keys():
		dicto[s] = dicto[s][1:] + dicto[s][:1]
	for (i, s) in enumerate(shoes):
		res[i] = dicto[s].pop(0)
	print(' '.join([str(k + 1) for k in res]))
for _ in range(int(input())):
	n = int(input())
	shoes = list(map(int, input().split()))
	solution(n, shoes)


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	x = list((i + 1 for i in range(a)))
	for j in range(a - 1):
		if b[j] == b[j + 1]:
			(x[j], x[j + 1]) = (x[j + 1], x[j])
	for k in range(len(x)):
		if k + 1 == x[k]:
			print(-1)
			break
	else:
		print(' '.join(map(str, x)))


T = int(input())
for t in range(T):
	n = int(input())
	s = [0] + list(map(int, input().split()))
	if n == 1:
		print(-1)
	else:
		result = True
		ans = []
		marker = [1]
		start = 1
		end = 1
		for i in range(2, n + 1):
			if s[i] == s[i - 1] and i < n:
				marker.append(i)
				end = i
			elif s[i] == s[i - 1] and i == n:
				marker.append(i)
				q = marker.pop()
				ans += [q] + marker
			elif s[i] > s[i - 1] and i == n:
				result = False
				break
			elif len(marker) == 1:
				result = False
				break
			else:
				start = i
				end = i
				q = marker.pop()
				ans += [q] + marker
				marker = [i]
		if not result:
			print(-1)
		else:
			print(' '.join(map(str, ans)))


for i in range(int(input())):
	n = int(input())
	sizes = list(map(int, input().split()))
	count = 1
	count_arr = []
	str = ''
	works = True
	for i in range(0, len(sizes) - 1):
		if sizes[i] == sizes[i + 1]:
			count += 1
		elif count == 1:
			works = False
			break
		else:
			count_arr.append(count)
			count = 1
	if count > 1:
		count_arr.append(count)
	else:
		works = False
	if len(count_arr) < 1:
		works = False
	if not works:
		print(-1)
		continue
	index = 1
	swap = 0
	for i in count_arr:
		swap = index
		for j in range(1, i):
			str += f'{index + j} '
		str += f'{swap} '
		index += i
	print(str)


cnt = int(input())
for i in range(cnt):
	input()
	nums = list(map(int, input().split()))
	dic = {}
	for (idx, num) in enumerate(nums):
		if num in dic:
			dic[num].append(idx)
		else:
			dic[num] = [idx]
	shuffle = ['0'] * len(nums)
	valid = True
	for idxs in dic.values():
		if len(idxs) == 1:
			print(-1)
			valid = False
			break
		for i in range(len(idxs)):
			shuffle[idxs[i]] = str(idxs[i - 1] + 1)
	if valid:
		print(' '.join(shuffle))


num_cases = int(input())
for _ in range(num_cases):
	num_students = int(input())
	sizes = input().split()
	result = []
	ind = 0
	ok = False
	end = False
	while True:
		actual_size = int(sizes[ind])
		start_ind = ind + 1
		end_ind = start_ind
		while True:
			ind += 1
			if ind == num_students:
				end = True
				break
			if actual_size == int(sizes[ind]):
				end_ind += 1
			else:
				break
		if end_ind > start_ind:
			result.append(end_ind)
			for i in range(start_ind, end_ind):
				result.append(i)
			if end:
				ok = True
				break
		else:
			break
	if not ok:
		print(-1)
	else:
		result = [str(n) for n in result]
		print(' '.join(result))


from itertools import groupby
T = int(input())
for case in range(T):
	n = int(input())
	x = map(int, input().split())
	s = []
	for (k, g) in groupby(x):
		l = sum((1 for i in g))
		if l == 1:
			print(-1)
			break
		t = len(s)
		s.append(t + l)
		for i in range(1, l):
			s.append(t + i)
	else:
		print(' '.join((str(y) for y in s)))


t = int(input())
for _ in range(t):
	n = int(input())
	size_old = 0
	student = 1
	not_single = False
	permutation = []
	remember_student = 1
	for number in input().split(' '):
		if student == 1:
			size_old = int(number)
			student += 1
			continue
		size_new = int(number)
		if not_single is False:
			if size_new == size_old:
				not_single = True
				permutation.append(student)
			else:
				break
		elif size_new == size_old:
			permutation.append(student)
		else:
			not_single = False
			permutation.append(remember_student)
			remember_student = student
		size_old = size_new
		student += 1
	if not_single is True:
		permutation.append(remember_student)
		result = ''
		for number in permutation:
			result += str(number) + ' '
		result = result[:-1]
		print(result)
	else:
		print('-1')


t = int(input())
for i in range(t):
	n = int(input())
	sizes = list(map(int, input().split()))
	res = [i for i in range(n)]
	isPossible = True
	for i in range(1, n):
		if sizes[i] == sizes[i - 1]:
			(res[i], res[i - 1]) = (res[i - 1], res[i])
	for i in range(n):
		if res[i] == i:
			isPossible = False
			break
		res[i] += 1
	if isPossible:
		print(' '.join(map(str, res)))
	else:
		print(-1)


t = int(input())
from collections import Counter, deque

def permute(shoes):
	shoes.append(shoes.popleft())
	return shoes
for _ in range(t):
	n = input()
	sizes = [int(s) for s in input().split()]
	count = Counter(sizes)
	if 1 in count.values():
		print(-1)
	else:
		StartIndex = dict()
		x = 1
		for s in count:
			StartIndex[s] = x
			x += count[s]
		output = []
		for s in count:
			new = deque([*range(StartIndex[s], StartIndex[s] + count[s])])
			output += list(permute(new))
		print(' '.join((str(o) for o in output)))


import collections

def solution(sizes):
	counter = collections.Counter(sizes)
	pairings = collections.defaultdict(list)
	for (i, size) in enumerate(sizes):
		pairings[size].append(i)
	p = [0 for _ in range(len(sizes))]
	for (size, idxs) in pairings.items():
		if len(idxs) == 1:
			return -1
		elif len(idxs) % 2 == 0:
			for i in range(0, len(idxs), 2):
				p[idxs[i + 1]] = idxs[i]
				p[idxs[i]] = idxs[i + 1]
		else:
			for i in range(len(idxs)):
				p[idxs[i]] = idxs[(i + 1) % len(idxs)]
	return ' '.join([str(i + 1) for i in p])
T = int(input())
results = []
for n in range(T):
	_ = int(input())
	sizes = list(map(int, input().split(' ')))
	results.append(solution(sizes))
for r in results:
	print(r)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	ans = ''
	start = 0
	flag = True
	while start < n:
		end = start
		for i in range(start + 1, n):
			if a[i] != a[start]:
				break
			else:
				end += 1
		if end == start:
			print('-1')
			flag = False
			break
		ans += str(end + 1) + ' '
		for idx in range(start, end):
			ans += str(idx + 1) + ' '
		start = end + 1
	if flag:
		print(ans)


trails = int(input())
answer_list = []
for x in range(trails):
	s = int(input())
	d = input().split(' ')
	dic = {}
	ans = ''
	for a in d:
		dic[a] = 0
	for p in d:
		dic[p] += 1
	count = 0
	for b in dic:
		ele = dic[b]
		if ele == 1:
			ans = '-1'
			break
		for k in range(2 + count, ele + 1 + count):
			ans += str(k)
			ans += ' '
		ans += str(1 + count)
		ans += ' '
		count += ele
	answer_list.append(ans)
for g in answer_list:
	print(g)


import sys
input = lambda : sys.stdin.readline().strip()
for Homu in range(int(input())):
	n = int(input())
	sizes = [int(i) for i in input().split()]
	jumps = [-1]
	for i in range(n - 1):
		if sizes[i] != sizes[i + 1]:
			jumps.append(i)
	jumps.append(n - 1)
	possible = True
	for i in range(len(jumps) - 1):
		if jumps[i + 1] - jumps[i] == 1:
			possible = False
			break
	if possible:
		ans = [0 for i in range(n)]
		for i in range(len(jumps) - 1):
			L = jumps[i] + 1
			R = jumps[i + 1]
			ans[R] = L + 1
			for i in range(L, R):
				ans[i] = i + 2
		ans = [str(i) for i in ans]
		print(' '.join(ans))
	else:
		print(-1)


for s in [*open(0)][2::2]:
	(*r,) = range(1, len((a := (s.split() + [0]))))
	i = j = 0
	p = a[0]
	for x in a:
		if x != p:
			if j - i < 2:
				r = (-1,)
				break
			r[i:j] = r[i + 1:j] + [r[i]]
			i = j
			p = a[i]
		j += 1
	print(*r)


total = int(input())
for i in range(total):
	n = int(input())
	l = [int(j) for j in input().split()]
	res = []
	(x, y) = (0, 0)
	fl = 1
	while y < n:
		if l[x] == l[y]:
			y += 1
			if y == n:
				if y - x < 2:
					print(-1)
					fl = 0
					break
				else:
					p = [o for o in range(x + 1, y + 1)]
					res += p[1:] + p[:1]
		elif y - x < 2:
			print(-1)
			fl = 0
			break
		else:
			p = [o for o in range(x + 1, y + 1)]
			res += p[1:] + p[:1]
			x = y
	if fl == 1:
		print(' '.join((str(m) for m in res)))


for _ in range(int(input())):
	n = int(input())
	l = [i for i in input().split(' ')]
	if n == 1:
		print(-1)
		continue
	nl = []
	(a, b) = (l[0], 1)
	m = 1
	res = True
	for i in l[1:]:
		m += 1
		if i == a:
			b += 1
			nl.append(m)
		elif b == 1:
			res = False
			break
		else:
			nl.append(m - b)
			a = i
			b = 1
	if b == 1:
		res = False
	else:
		nl.append(m - b + 1)
	if res:
		print(*nl)
	else:
		print(-1)


from collections import defaultdict as dd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = dd(list)
	for x in range(n):
		d[a[x]].append(x + 1)
	ans = [0] * n
	flag = True
	for x in d.values():
		if len(x) == 1:
			flag = False
			break
		for y in range(len(x) - 1):
			ans[x[y] - 1] = x[y + 1]
		ans[x[len(x) - 1] - 1] = x[0]
	if flag:
		print(' '.join(list(map(str, ans))))
	else:
		print(-1)


num_of_cases = int(input())
for _ in range(num_of_cases):
	N = int(input())
	arr = [int(x) for x in input().split(' ')]
	if N == 1:
		print(-1)
	else:
		res = []
		cur = arr[0]
		straight = 1
		idx = 1
		not_ok = False
		while idx < N:
			if arr[idx] == cur:
				straight += 1
				idx += 1
			elif straight == 1:
				print(-1)
				not_ok = True
				break
			else:
				start = len(res) + 1
				end = idx
				tmp = [x for x in range(start + 1, end + 1)] + [start]
				res.extend(tmp)
				cur = arr[idx]
				idx += 1
				straight = 1
		if not not_ok:
			if straight == 1:
				print(-1)
				not_ok = True
			else:
				start = len(res) + 1
				tmp = [x for x in range(start + 1, N + 1)] + [start]
				res.extend(tmp)
				print(' '.join([str(x) for x in res]))


def op(s, p):
	A = ''
	for se in s:
		A += str(se) + p
	return A[:-1]

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

def a():
	return int(input())

def kil_(n, a):
	m = dict()
	m[a[0]] = 1
	a1 = a[0]
	for i in range(1, n):
		if a[i] == a1:
			m[a1] += 1
		else:
			a1 = a[i]
			m[a1] = 1
	for (x, y) in m.items():
		if not y > 1:
			return '-1'
	j = 0
	d = []
	while j < len(a):
		ok = a[j]
		kj = m[ok] + j
		for i in range(m[ok]):
			d.append(kj)
			kj = i + j + 1
		j = kj
	return op(d, ' ')

def kil(a):
	t = int(input())
	A = ''
	for i in range(t):
		A += kil_(a(), fu()) + '\n'
	print(A[:-1])
kil(a)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	d = Counter(A)
	s1 = []
	s = 0
	for k in d:
		s1.append(k)
		if d[k] == 1:
			s = -1
			break
	ans = []
	l1 = 0
	l2 = 0
	if s == 0:
		for j in range(len(d)):
			ans.append(l1 + d[s1[j]])
			l1 += d[s1[j]]
			for i in range(l2 + 1, l1):
				ans.append(i)
			l2 += d[s1[j]]
		s2 = ''
		for ele in ans:
			s2 += str(ele) + ' '
		print(s2)
	else:
		print(-1)


def solve(n, a):
	p = True
	k = [i for i in range(1, n + 1)]
	if n == 1:
		return [-1]
	for i in range(1, n):
		if a[i - 1] == a[i]:
			(k[i - 1], k[i]) = (k[i], k[i - 1])
			p = False
		else:
			if p or i == n - 1:
				return ['-1']
			p = True
	return k
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(*solve(n, a))


from collections import defaultdict, deque
test_cases = int(input())

def handle():
	input()
	values = input().split(' ')
	values_by_index = defaultdict(lambda : deque())
	for (index, value) in enumerate(values):
		values_by_index[value].append(index)
	result = []
	for (index, value) in enumerate(values):
		if value not in values_by_index or (len(values_by_index[value]) == 1 and values_by_index[value][0] == index):
			return -1
		if index == values_by_index[value][-1]:
			result.append(str(values_by_index[value].popleft() + 1))
		else:
			result.append(str(values_by_index[value].pop() + 1))
		if len(values_by_index[value]) == 0:
			del values_by_index[value]
	return ' '.join(result)
for _ in range(test_cases):
	print(handle())


t = int(input())
for _ in range(t):
	n = int(input())
	m = {}
	for s_i in map(int, input().split()):
		m[s_i] = m.get(s_i, 0) + 1
	if any((v == 1 for v in m.values())):
		print(-1)
	else:
		p = ''
		c = 0
		for k in sorted(m.keys()):
			v = m[k]
			c += v
			p += f'{c} ' + ' '.join((str(x) for x in range(c - v + 1, c))) + ' '
		print(p)


import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	if n == 1:
		print(-1)
		return
	k = 0
	prev = A[0]
	c = 1
	a = []
	for i in range(1, n):
		if A[i] == prev:
			c += 1
			a.append(i + 1)
		elif c == 1:
			print(-1)
			c = 1
			return
		else:
			a.append(k + 1)
			c = 1
			k = i
			prev = A[k]
	if c == 1:
		print(-1)
		return
	a.append(k + 1)
	print(*a)
t = int(input())
while t != 0:
	solve()
	t -= 1


n = int(input())
for i in range(n):
	k = int(input())
	arr = list(map(int, input().split()))
	brr = set(arr)
	if len(brr) == len(arr):
		print('-1')
		continue
	if arr[-1] != arr[-2]:
		print('-1')
		continue
	crr = []
	crr.append(1)
	for j in range(k - 1):
		crr.append(j + 2)
		if arr[j] == arr[j + 1]:
			temp = crr[j]
			crr[j] = crr[j + 1]
			crr[j + 1] = temp
	for j in range(k):
		if crr[j] == j + 1:
			print(-1)
			break
	else:
		print(' '.join(map(str, crr)))


for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	d = dict()
	for i in range(len(ls)):
		if ls[i] in d:
			d[ls[i]].append(i + 1)
		else:
			d[ls[i]] = [i + 1]
	res = [0] * n
	isPossible = True
	for (k, v) in d.items():
		if len(v) > 1:
			for i in range(len(v) - 1):
				res[v[i] - 1] = v[i + 1]
			res[v[-1] - 1] = v[0]
		else:
			isPossible = False
			break
	if isPossible:
		print(' '.join(map(str, res)))
	else:
		print(str(-1))


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	counts = Counter(nums)
	f = False
	for i in counts.keys():
		if counts[i] == 1:
			f = True
			print(-1)
			break
	if not f:
		l = [0]
		for i in range(1, n):
			if nums[i] != nums[i - 1]:
				l.append(i)
		l.append(n)
		ans = []
		i = 0
		while i < len(l) - 1:
			ans.append(l[i + 1] - 1)
			for j in range(l[i], l[i + 1] - 1):
				ans.append(j)
			i += 1
		for i in range(len(ans)):
			ans[i] += 1
		print(' '.join(map(str, ans)))


from collections import defaultdict

def shoe_shuffle(n, arr):
	my_data = defaultdict(list)
	for (idx, ele) in enumerate(arr, start=1):
		my_data[ele].append(idx)
	ans = []
	for each in my_data:
		if len(my_data[each]) < 2:
			return [-1]
		ele = my_data[each].pop()
		my_data[each].insert(0, ele)
		ans.extend(my_data[each])
	return ans
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	print(*shoe_shuffle(n, arr))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = [0] * n
	i = n - 1
	r = n
	while i > 0:
		if arr[i] == arr[i - 1]:
			brr[i] = i - 1 + 1
			brr[i - 1] = r
		else:
			r = i
		i -= 1
	if sum(brr) == n * (n + 1) // 2:
		print(*brr)
	else:
		print(-1)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = Counter(l)
	if any((x == 1 for x in c.values())):
		print(-1)
		continue
	print(*[i if i != 0 and l[i] == l[i - 1] else i + c[l[i]] for i in range(n)])


def resi():
	n = int(input())
	a = list(map(int, input().split()))
	p = []
	d = 1
	for i in range(1, n):
		if a[i] == a[i - 1]:
			d += 1
			p.append(i + 1)
		else:
			if d == 1:
				print('-1')
				return
			p.append(i + 1 - d)
			d = 1
	if d == 1:
		print('-1')
		return
	if d > 1:
		p.append(n + 1 - d)
	for i in range(n):
		print(p[i], end=' ')
	print()
	return
for _ in range(int(input())):
	resi()


def resi():
	j = int(input())
	m = list(map(int, input().split()))
	s = []
	r = 1
	for i in range(1, j):
		if m[i] == m[i - 1]:
			r += 1
			s.append(i + 1)
		else:
			if r == 1:
				print('-1')
				return
			s.append(i + 1 - r)
			r = 1
	if r == 1:
		print('-1')
		return
	if r > 1:
		s.append(j + 1 - r)
	for i in range(j):
		print(s[i], end=' ')
	print()
	return
for _ in range(int(input())):
	resi()


xx = int(input())

def cal(n, arr):
	if n == 1:
		return [-1]
	s = 0
	ans = []
	a = arr[0]
	for i in range(1, n):
		if arr[i] != a:
			if i == s + 1:
				return [-1]
			else:
				ans += [i] + list(range(s + 1, i))
				s = i
				a = arr[i]
		elif i == n - 1:
			ans += [i + 1] + list(range(s + 1, i + 1))
	if len(ans) < n:
		return [-1]
	return ans
for jj in range(xx):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	print(*cal(n, arr))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	x = a[0]
	p = 0
	z = []
	v = 1
	for i in range(1, n):
		if a[i] != x:
			if c == 0:
				v = 0
				break
			else:
				z.append(p + 1)
				p = i
				c = 0
				x = a[i]
		else:
			z.append(i + 1)
			c += 1
	if v == 1 and c > 0:
		z.append(p + 1)
		print(*z)
	else:
		print(-1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	w = [0] * n
	j = n - 1
	k = n
	while j > 0:
		if l[j] == l[j - 1]:
			w[j] = j
			w[j - 1] = k
		else:
			k = j
		j -= 1
	if sum(w) == n * (n + 1) // 2:
		print(*w)
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.append(-1)
	ans = []
	a = 2
	s = 1
	k = 0
	ch = ''
	test = True
	for j in range(n):
		if l[j] == l[j + 1]:
			s = s + 1
			ans.append(a)
			a = a + 1
		else:
			ans.append(k + 1)
			if s == 1:
				print(-1)
				test = False
				break
			else:
				k = j + 1
				s = 1
				a = k + 2
	if test == True:
		print(*ans)


for _ in range(int(input())):
	n = int(input())
	ms = list(map(int, input().split())) + [-1]
	l = 0
	out = []
	for i in range(1, n + 1):
		if ms[i] != ms[i - 1]:
			if l + 1 == i:
				out = [-1]
				break
			out += [i] + list(range(l + 1, i))
			l = i
	print(*out)


t = int(input())
ans = []
for i in range(t):
	n = int(input())
	shoes = list(map(int, input().split(' ')))
	tailles = {}
	for (i, shoe) in enumerate(shoes):
		if shoe not in tailles:
			tailles[shoe] = [i]
		else:
			tailles[shoe].append(i)
	permut = []
	for taille in tailles.values():
		if len(taille) == 1:
			permut = -1
	if permut != -1:
		for shoe in shoes:
			nb = len(tailles[shoe])
			if nb > 1:
				permut.append(1 + tailles[shoe].pop(1))
			else:
				permut.append(1 + tailles[shoe].pop(0))
	ans.append(permut)
for i in ans:
	if i == -1:
		print(i)
	else:
		print(' '.join(map(str, i)))


from itertools import count
from typing import List, Optional
import collections as co
import copy

class Solution:

	def cambiar(self, m):
		m[0] += 1
		m[1] += 1
		ret = ''
		for x in range(m[0] + 1, m[1] + 1):
			ret += str(x) + ' '
		ret += str(m[0]) + ' '
		return ret

	def buscar(self, v, pos):
		valor = v[pos]
		while pos >= 0 and valor == v[pos]:
			pos -= 1
		return pos

	def solve(self, v):
		m = []
		pos = len(v) - 1
		while pos != -1:
			nuevapos = self.buscar(v, pos)
			dif = pos - nuevapos
			if dif == 1:
				return -1
			m.append([nuevapos + 1, pos])
			pos = nuevapos
		tam = len(m) - 1
		res = ''
		for i in range(tam, -1, -1):
			seg = m[i]
			ret = self.cambiar(seg)
			res += ret
		return res.strip()
sol = Solution()
for _ in range(int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	print(sol.solve(v))


import sys
from collections import defaultdict
input = sys.stdin.readline

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

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
tc = inp()
while tc:
	n = inp()
	seq = list(invr())
	chunks = []
	prevChunkStart = 0
	prevElem = -1
	for (i, elem) in enumerate(seq):
		if elem != prevElem and prevElem != -1:
			chunks.append([prevChunkStart, i - 1])
			prevChunkStart = i
		if i == len(seq) - 1:
			chunks.append([prevChunkStart, i])
		prevElem = elem
	ans = []
	for chunk in chunks:
		(si, ei) = chunk
		if si == ei:
			ans = [-1]
			break
		else:
			ans += [i + 1 for i in range(si + 1, ei + 1)]
			ans += [si + 1]
	print(' '.join(map(str, ans)))
	tc -= 1


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	if n == 1:
		print(-1)
	else:
		flag = 0
		if list1[0] != list1[1]:
			flag = 1
		else:
			for i in range(1, n - 1, 1):
				if list1[i] == list1[i + 1] or list1[i] == list1[i - 1]:
					flag = 0
				else:
					flag = 1
					break
			if list1[n - 2] != list1[n - 1]:
				flag = 1
		if flag == 1:
			print(-1)
		else:
			s = ''
			i = 0
			while i < n - 1:
				j = i
				while i < n - 1 and list1[i] == list1[i + 1]:
					s += str(i + 1 + 1) + ' '
					i += 1
				s += str(j + 1) + ' '
				i += 1
			print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = {}
	s = []
	f = 0
	for i in set(a):
		b[i] = []
	for i in range(n):
		b[a[i]] += [i]
		s.append(0)
	for i in b.values():
		if len(i) == 1:
			f = -1
			break
		else:
			k = i[-1:] + i[:-1]
			for j in range(len(i)):
				s[i[j]] = str(k[j] + 1)
	if f == -1:
		print(f)
	else:
		print(' '.join(s))


class ShoeShuffling:

	def solve(self, n, s):
		if n == 1:
			print(-1)
			return
		shuffle = []
		start = 0
		for i in range(1, n):
			if s[i] == s[start]:
				shuffle.append(i)
			elif i == start + 1:
				print(-1)
				return
			else:
				shuffle.append(start)
				start = i
		if start == n - 1:
			print(-1)
			return
		shuffle.append(start)
		for j in shuffle:
			print(j + 1, end=' ')
		print()
		return
T = int(input())
while T:
	T -= 1
	n = int(input())
	s = list(map(int, input().split()))
	ShoeShuffling().solve(n, s)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	c = Counter(s)
	f = 0
	for i in c.keys():
		if c[i] < 2:
			f = 1
			break
	if f:
		print(-1)
	else:
		ans = []
		cur = s[0]
		j = 0
		for i in range(1, n):
			if s[i] == cur:
				ans.append(i + 1)
			else:
				ans.append(j + 1)
				j = i
				cur = s[i]
		ans.append(j + 1)
		print(*ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.append(0)
	ans = [0] * n
	s = -1
	for i in range(n):
		if a[i] == a[i + 1]:
			ans[i] = i + 2
			if i == 0 or a[i - 1] != a[i]:
				s = i + 1
		else:
			if s == -1:
				print(-1)
				break
			ans[i] = s
			s = -1
	else:
		print(*ans)


t = int(input())
for _ in range(t):
	n = int(input())
	s = list(map(int, input().split(' ')))
	if n == 1:
		print(-1)
		continue
	if s[0] != s[1]:
		print(-1)
		continue
	l = [i for i in range(1, n + 1)]
	k = 1
	flag = True
	for i in range(n - 1, 0, -1):
		if s[i] == s[i - 1]:
			k += 1
			(l[i], l[i - 1]) = (l[i - 1], l[i])
		elif s[i] != s[i - 1] and k == 1:
			print(-1)
			flag = False
			break
		else:
			k = 1
	if flag == True:
		print(*l)