Polycarp wrote on a whiteboard an array $p$ of length $n$, which is a permutation of numbers from $1$ to $n$. In other words, in $p$ each number from $1$ to $n$ occurs exactly once.

He also prepared a resulting array $a$, which is initially empty (that is, it has a length of $0$).

After that, he did exactly $n$ steps. Each step looked like this:

Look at the leftmost and rightmost elements of $p$, and pick the smaller of the two.

If you picked the leftmost element of $p$, append it to the left of $a$; otherwise, if you picked the rightmost element of $p$, append it to the right of $a$.

The picked element is erased from $p$.

Note that on the last step, $p$ has a length of $1$ and its minimum element is both leftmost and rightmost. In this case, Polycarp can choose what role the minimum element plays. In other words, this element can be added to $a$ both on the left and on the right (at the discretion of Polycarp).

Let's look at an example. Let $n=4$, $p=[3, 1, 4, 2]$. Initially $a=[]$. Then:

During the first step, the minimum is on the right (with a value of $2$), so after this step, $p=[3,1,4]$ and $a=[2]$ (he added the value $2$ to the right).

During the second step, the minimum is on the left (with a value of $3$), so after this step, $p=[1,4]$ and $a=[3,2]$ (he added the value $3$ to the left).

During the third step, the minimum is on the left (with a value of $1$), so after this step, $p=[4]$ and $a=[1,3,2]$ (he added the value $1$ to the left).

During the fourth step, the minimum is both left and right (this value is $4$). Let's say Polycarp chose the right option. After this step, $p=[]$ and $a=[1,3,2,4]$ (he added the value $4$ to the right).

Thus, a possible value of $a$ after $n$ steps could be $a=[1,3,2,4]$.

You are given the final value of the resulting array $a$. Find any possible initial value for $p$ that can result the given $a$, or determine that there is no solution.


-----Input-----

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

Each test case consists of two lines. The first of them contains an integer $n$ ($1 \le n \le 2\cdot10^5$) — the length of the array $a$. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the elements of the array $a$. All elements of the $a$ array are distinct numbers.

It is guaranteed that the sum of the values $n$ over all test cases in the test does not exceed $2\cdot10^5$.


-----Output-----

Print $t$ lines, each of the lines must contain the answer to the corresponding set of input data: numbers $p_1, p_2, \dots, p_n$  — any of the possible initial values of the array $p$, which will lead to the given array $a$. All elements of $p$ are distinct integers from $1$ to $n$. Thus, if there are several solutions, print any. If there is no solution, then print -1 on the line.


-----Examples-----

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


-----Note-----

The first test case in the example is clarified in the main section of the problem statement. There may be other correct answers for this test set.

In the second test case, $n=1$. Thus, there is only one permutation that can be the answer: $p=[1]$. Indeed, this is the answer to this test case.

In the third test case of the example, no matter what permutation you take as $p$, after applying the $n$ steps, the result will differ from $a=[1, 3, 5, 4, 2]$.

Difficulty: EASY
Tags: Constructive algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = input()
	x = list(input().split())
	if x[0] == n:
		t = x.pop(0)
	elif x[-1] == n:
		t = x.pop(0)
	else:
		print(-1)
		continue
	x.reverse()
	x.append(t)
	print(' '.join(x))


def recover(n, L):
	if n == 1:
		return 1
	if int(L[0]) == n or int(L[-1]) == n:
		L.remove(str(n))
		L.reverse()
		L.append(str(n))
		return ' '.join(L)
	return -1
total = int(input())
for i in range(total):
	n = int(input())
	L = input().split()
	print(recover(n, L))


n = int(input())
for p in range(n):
	i = int(input())
	a = list(map(int, input().split()))
	b = []
	if max(a) != a[0] and max(a) != a[-1]:
		print('-1')
		continue
	p = reversed(a)
	print(' '.join(map(str, p)))


t = int(input())
ns = []
arr = []
for _ in range(t):
	ns.append(int(input()))
	arr.append(list(map(int, input().split(' '))))
for a in arr:
	a.reverse()
	if max(a) in (a[0], a[-1]):
		print(' '.join(tuple(map(str, a))))
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	if a[-1] != m and a[0] != m:
		print(-1)
	elif a[0] == m:
		p = [m] + a[1:][::-1]
		print(' '.join(map(str, p)))
	else:
		p = a[:-1][::-1] + [m]
		print(' '.join(map(str, p)))


def main():
	passn = int(input())
	arr = list(map(int, input().split()))
	m = max(arr)
	if m == arr[0]:
		print(arr[0], ' '.join(map(str, arr[-1:0:-1])))
		return
	if m == arr[-1]:
		print(' '.join(map(str, arr[-2::-1])), arr[-1])
		return
	print(-1)
for i in range(int(input())):
	main()


import math

def intlist():
	return [int(i) for i in input().split(' ')]

def stringlsit():
	return input().split(' ')

def solve():
	n = int(input())
	a = intlist()
	ans = []
	t = 1
	if a[0] != n and a[-1] != n:
		return -1
	if a[0] == n:
		ans.append(n)
		a.pop(0)
	else:
		ans.append(n)
		a.pop(n - 1)
	a = a[::-1]
	ans = a + ans
	ans = [str(i) for i in ans]
	return ' '.join(ans)
t = input()
for tt in range(int(t)):
	print(solve())


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = []
	if max(a) != a[0] and max(a) != a[-1]:
		print(-1)
		continue
	p = reversed(a)
	print(' '.join(map(str, p)))


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	data = list(map(int, input().split()))
	answer = []
	if data[0] == n:
		answer = [n] + data[:0:-1]
		print(' '.join(map(str, answer)))
	elif data[-1] == n:
		answer = data[::-1]
		print(' '.join(map(str, answer)))
	else:
		print(-1)


def main():
	T = int(input())
	for t in range(T):
		n = input()
		num = list(map(int, input().strip().split(' ')))
		maxi = max(num)
		if num[-1] == maxi or num[0] == maxi:
			num.remove(maxi)
			num = num[::-1] + [maxi]
			print(' '.join(map(str, num)))
		else:
			print(-1)
main()


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	if s[0] == n or s[n - 1] == n:
		print((' '.join((str(i) for i in reversed(s[:s.index(n)]))) + ' ' + ' '.join((str(i) for i in reversed(s[s.index(n):])))).lstrip().rstrip())
	else:
		print(-1)


from collections import deque

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	i = l.index(max(l))
	if i != 0 and i != n - 1:
		return -1
	if i == 0:
		return ' '.join(map(str, [l[0]] + l[1:][::-1]))
	if i == n - 1:
		return ' '.join(map(str, l[:-1][::-1] + [l[-1]]))
n = int(input())
for i in range(n):
	print(solve())


t = int(input())
answers = []
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	if a[0] == n:
		a = [a[0]] + list(reversed(a[1:]))
	elif a[n - 1] == n:
		a = list(reversed(a[:n - 1])) + [a[n - 1]]
	else:
		a = [-1]
	print(' '.join([str(x) for x in a]))


_ = int(input())
for __ in range(_):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr[0] != n and arr[-1] != n:
		print(-1)
		continue
	if arr[0] == n:
		arr_out = [n]
		arr_tmp = arr[1:]
		arr_tmp.reverse()
		arr_out += arr_tmp
		print(' '.join([str(x) for x in arr_out]))
	else:
		arr_tmp = arr[:-1]
		arr_tmp.reverse()
		arr_tmp.append(n)
		print(' '.join([str(x) for x in arr_tmp]))


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	arr = [int(x) for x in sys.stdin.readline().split()]
	m = max(arr)
	if arr[0] != m and arr[len(arr) - 1] != m:
		print(-1)
		continue
	arr.remove(m)
	arr = arr[::-1]
	arr.append(m)
	print(' '.join(map(str, arr)))


import math

def intlist():
	return [int(i) for i in input().split(' ')]

def stringlsit():
	return input().split(' ')

def printjoin(l):
	l = [str(i) for i in l]
	return ' '.join(l)

def solve():
	n = int(input())
	a = intlist()
	if a[0] == n:
		return printjoin([a[0]] + a[-1:0:-1])
	if a[-1] == n:
		return printjoin([a[-1]] + a[-2:0:-1] + [a[0]])
	return -1
t = input()
for tt in range(int(t)):
	print(solve())


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	a = max(w)
	if w[0] != max(w) and w[-1] != max(w):
		print(-1)
	else:
		if w[0] == max(w):
			w = w[1:][::-1] + [w[0]]
		elif w[-1] == max(w):
			w = w[:-1][::-1] + [w[-1]]
		print(' '.join(map(str, w)))


k = []
for i in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	y = max(p)
	if p.index(max(p)) == 0 or p.index(y) == len(p) - 1:
		p.pop(p.index(y))
		p.reverse()
		p.append(y)
		s = ' '.join((str(j) for j in p))
		k.append(s)
	else:
		k.append(-1)
for t in k:
	print(t)


def examine(nums):
	if not nums[0] == len(nums) and (not nums[-1] == len(nums)):
		return (False, nums)
	return (True, nums[::-1])
t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(num) for num in input().split(' ')]
	(possible, original) = examine(nums)
	if not possible:
		print(-1)
	else:
		print(' '.join((str(k) for k in original)))


get_int = lambda : int(input())
get_int_list = lambda : list(map(int, input().split()))

def solve():
	n = get_int()
	ar = get_int_list()
	if ar[0] != n and ar[n - 1] != n:
		return [-1]
	grow_left = []
	grow_right = []
	left = 0
	right = n - 1
	while left <= right:
		if ar[left] < ar[right]:
			grow_right.append(ar[right])
			right -= 1
		else:
			grow_left.append(ar[left])
			left += 1
	grow_left.reverse()
	return grow_left + grow_right
t = get_int()
for _ in range(t):
	print(' '.join(map(str, solve())))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	if a[0] != m and a[-1] != m:
		print(-1)
	elif n == 1:
		print(a[0])
	else:
		ans = []
		if n % 2 == 0:
			for i in range(n // 2 - 1, -1, -1):
				ans.append(a[i])
			for i in range(n - 1, n // 2 - 1, -1):
				ans.append(a[i])
		else:
			for i in range(n // 2 - 1, -1, -1):
				ans.append(a[i])
			for i in range(n - 1, n // 2 - 1, -1):
				ans.append(a[i])
		print(' '.join(list(map(str, ans))))
	t -= 1


from collections import deque

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a = deque(a)
	if n == a[0] or n == a[-1]:
		p = deque()
		while a:
			if a[0] >= a[-1]:
				p.appendleft(a.popleft())
			else:
				p.append(a.pop())
		print(' '.join((str(x) for x in p)))
	else:
		print(-1)
for test in range(int(input())):
	solve()


n = int(input())
while n > 0:
	N = int(input())
	nums = list(map(int, input().split(' ')))
	if nums[0] == N or nums[len(nums) - 1] == N:
		ans = []
		if nums[0] == N:
			ans.append(N)
			for i in range(len(nums) - 1, 0, -1):
				ans.append(nums[i])
		else:
			ans = nums[:-1][::-1]
			ans.append(N)
		print(' '.join((str(item) for item in ans)))
	else:
		print('-1')
	n -= 1


t = int(input())
for a in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr[0] != n and arr[n - 1] != n:
		print(-1)
	else:
		ans = []
		for i in range(n - 1, -1, -1):
			ans.append(str(arr[i]))
		print(' '.join(ans))


from collections import deque

def solution(n, nums):
	nums = deque(nums)
	(pos, max_) = (0, 0)
	for (i, num) in enumerate(nums):
		if num > max_:
			max_ = num
			pos = i
	if pos != 0 and pos != n - 1:
		print('-1')
		return
	res = deque([])
	if pos == 0:
		res.append(nums[0])
		nums.popleft()
	else:
		res.append(nums[n - 1])
		nums.pop()
	while nums:
		if nums[0] > nums[-1]:
			res.appendleft(nums[0])
			nums.popleft()
		else:
			res.append(nums[-1])
			nums.pop()
	print(' '.join((str(s) for s in res)))
t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(x) for x in input().split()]
	solution(n, nums)


for s in [*open(0)][2::2]:
	print(*((a := s.split()[::-1]), [-1])[a[0] != str(len(a)) != a[-1]])


t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = a.index(max(a))
	if b == 0 or b == n - 1:
		a1 = []
		for r in range(n // 2):
			a1.append(str(a[n // 2 - 1 - r]))
		for k in range(n // 2, n):
			a1.append(str(a[n + n // 2 - 1 - k]))
		print(' '.join(a1))
	else:
		print(-1)


def recover_permutation(n, a):
	p = 0
	q = n - 1
	if not (a[p] == n or a[q] == n):
		return '-1'
	ans = []
	while p <= q:
		if a[p] < a[q]:
			ans.insert(0, a[p])
			p += 1
		else:
			ans.append(a[q])
			q -= 1
	return ' '.join((str(ele) for ele in ans))

def recover_permutation1(n, a):
	p = 0
	q = n - 1
	if not (a[p] == n or a[q] == n):
		return '-1'
	ans = ''
	mid = n // 2
	for i in range(mid, -1, -1):
		ans += str(a[i]) + ' '
	for i in range(n - 1, mid, -1):
		ans += str(a[i]) + ' '
	return ans[:-1]
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	print(recover_permutation1(n, a))


for R in [*open(0)][2::2]:
	print(*((a := R.split()[::-1]), [-1])[a[0] != str(len(a)) != a[-1]])


import sys
import bisect
import math
from collections import deque
input = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 9

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] != n and a[-1] != n:
		return -1
	else:
		queue = deque()
		(l, r) = (0, n - 1)
		while l < r:
			if a[l] < a[r]:
				queue.appendleft(a[l])
				l += 1
			else:
				queue.append(a[r])
				r -= 1
		queue.append(a[l])
	return ' '.join((str(x) for x in queue))
t = 1
t = int(input())
for _ in range(t):
	print(solve())


for t in range(int(input())):
	n = input()
	a = input().split()
	if n in [a[0], a[-1]]:
		print(*a[::-1])
	else:
		print(-1)


for _ in range(int(input())):
	n = input()
	array = input().split()
	if array[0] != n and array[len(array) - 1] != n:
		print(-1)
	else:
		print(*array[::-1])


for s in [*open(0)][2::2]:
	if (n := str(len((a := s.split()[::-1])))) != a[0]:
		a = (a.pop(), *a)
	print(*(a, [-1])[a[0] != n])


for caseno in range(int(input())):
	n = input()
	a = input().split()
	p = [n]
	answer = []
	if int(n) <= 2:
		answer = a
	elif a[0] == n:
		a = a[1:]
		answer = a[:1] + p + a[1:][::-1]
	elif a[-1] == n:
		a = a[:-1]
		answer = a[:1] + p + a[1:][::-1]
	else:
		answer = ['-1']
	print(*answer)


for s in [*open(0)][2::2]:
	a = s.split()[::-1]
	i = a.index(str((n := len(a))))
	print(*([n] + a[:i] + a[i + 1:], [-1])[0 != i != n - 1])


n = int(input())

def per():
	l = int(input())
	a = [int(x) for x in input().split()]
	s = str()
	if a[0] != l and a[l - 1] != l:
		print('-1')
	else:
		for i in range(len(a) - 1, -1, -1):
			s += str(a[i]) + ' '
		print(s)
for i in range(n):
	per()


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(i) for i in input().split()]
	if nums[0] != max(nums) and nums[-1] != max(nums):
		print(-1)
	else:
		(l, r) = (0, len(nums) - 1)
		ans = deque()
		while l <= r:
			if nums[r] < nums[l]:
				ans.append(nums[r])
				r -= 1
			else:
				ans.appendleft(nums[l])
				l += 1
		print(' '.join([str(i) for i in list(ans)]))


num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
for s in [*open(0)][2::2]:
	print(*((a := s.split()[::-1]), [-1])[a[0] != str(len(a)) != a[-1]])


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = ''
	if a[0] != n and a[n - 1] != n:
		print('-1')
	else:
		i = n - 1
		while i >= 0:
			s += str(a[i]) + ' '
			i -= 1
		print(s)


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		lst = list(map(int, input().split()))
		print(*list(reversed(lst))) if lst[-1] == n or lst[0] == n else print(-1)
main()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] == n or a[n - 1] == n:
		print(*reversed(a))
	else:
		print(-1)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	if max(a) != a[0] and max(a) != a[n - 1]:
		print(-1)
	else:
		c = (n - 1) // 2
		x = a[0:c + 1]
		y = a[c + 1:n]
		x.reverse()
		y.reverse()
		print(*x, *y)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n != a[0] and n != a[-1]:
		print(-1)
	else:
		print(*a[::-1])


t = int(input())
ret = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		ret.append([n])
		continue
	if a[0] != n and a[-1] != n:
		ret.append([-1])
	else:
		if a[0] == n:
			ans = a[1:][::-1]
			ans.extend([a[0]])
		else:
			ans = [a[-1]]
			ans.extend(a[:-1][::-1])
		ret.append(ans)
for i in ret:
	print(*i)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n != l[0] and n != l[-1]:
		print(-1)
	else:
		l.remove(n)
		i = len(l) // 2
		print(*l[i - 1::-1] + [n] + l[n - 1:i - 1:-1])


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a[-1] != n and a[0] != n:
		print(-1)
	elif n == 1:
		print(*a)
	else:
		print(*a[::-1])


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	mx = max(a)
	if a[0] == mx or a[-1] == mx:
		if mx == a[0]:
			b = a[1:]
		else:
			b = a[:n - 1]
		b.reverse()
		b.append(mx)
		print(*b)
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	k = n
	p = []
	if a[-1] != max(a) != a[0]:
		print(-1)
	else:
		b = max(a[0], a[-1])
		p.append(b)
		a.remove(b)
		a.reverse()
		print(*p + a)


for i in range(int(input())):
	(a, s) = (int(input()), list(map(int, input().split())))
	l = list()
	if a != s[0] and a != s[-1]:
		print(-1)
	else:
		l.append(a)
		s.remove(a)
		l += reversed(s)
		print(*l)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr[0] == n or arr[n - 1] == n:
		print(*arr[::-1])
	else:
		print(-1)


T = int(input())
for t in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	if A[0] == n or A[-1] == n:
		print(*reversed(A))
	else:
		print(-1)


import sys
import math
from bisect import bisect_right as br
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	mx = max(arr)
	if arr[0] != mx and arr[-1] != mx:
		print(-1)
		continue
	arr.remove(mx)
	arr.reverse()
	print(mx, *arr)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] == n or a[n - 1] == n:
		print(*a[::-1])
	else:
		print(-1)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] == n:
		a = a[1:]
		print(n, *a[::-1])
	elif a[-1] == n:
		a.pop()
		print(*a[::-1], n)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr.index(max(arr)) in [0, len(arr) - 1]:
		print(*arr[::-1])
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	m = max(p)
	if m == p[0] or m == p[-1]:
		print(*p[::-1])
	else:
		print(-1)


T = int(input())
while T > 0:
	N = int(input())
	p = list(map(int, input().split()))
	if p[0] == N:
		p[1:N] = reversed(p[1:N])
		print(*p)
	elif p[N - 1] == N:
		p[0:N - 1] = reversed(p[0:N - 1])
		print(*p)
	else:
		print(-1)
	T -= 1


t = int(input())
while t > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	if l[0] == n:
		l = l[-1:0:-1] + l[0:1]
		print(*l)
	elif l[-1] == n:
		l = l[-2::-1] + l[n - 1:n]
		print(*l)
	else:
		print(-1)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = [int(num) for num in input().split()]
	if a[-1] != n and a[0] != n:
		print(-1)
		continue
	elif n == 1:
		print(1)
		continue
	elif a[-1] == n:
		x = a[-2::-1] + [n]
		print(*x)
		continue
	elif a[0] == n:
		x = [n] + a[-1:0:-1]
		print(*x)


a = int(input())
for k in range(a):
	b = int(input())
	if b == 1:
		array = input().split()
		print(1)
	else:
		array = input().split()
		if int(array[0]) == b:
			print(array[0], end=' ')
			for i in range(1, b):
				print(array[b - i], end=' ')
		elif int(array[b - 1]) == b:
			for i in range(1, b):
				print(array[b - i - 1], end=' ')
			print(array[b - 1], end=' ')
		else:
			print(-1, end=' ')
		print('')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(*a)
	else:
		k = a.index(n)
		if k == 0 or k == n - 1:
			print(*a[::-1])
		else:
			print(-1)


t = int(input())
for _ in range(t):
	not_important = input()
	p = [int(number) for number in input().split(' ')]
	if max(p[0], p[-1]) < max(p):
		print(-1)
	else:
		p.reverse()
		result = ''
		for number in p:
			result += str(number) + ' '
		result = result[:-1]
		print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	k = [int(x) for x in input().split(' ')]
	if k[0] == n or k[-1] == n:
		k.reverse()
		print(*k)
	else:
		print(-1)


t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mx = max(arr)
	if arr[0] != mx and arr[-1] != mx:
		print(-1)
		continue
	if arr[0] == mx:
		res = arr[::-1]
		print(*res[:-1] + [mx])
	else:
		res = arr[::-1]
		print(*res[1:] + [mx])


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	max_lis = max(lis[0], lis[-1])
	if max_lis != n:
		print('-1')
	else:
		print(*lis[::-1])


arr = []
for i in range(int(input())):
	input()
	arr.append(list(map(int, input().split())))
for a in arr:
	maximum = max(a)
	if maximum == a[0] or maximum == a[-1]:
		print(*a[::-1])
	else:
		print(-1)


for _ in range(int(input())):
	x = int(input())
	z = list(map(int, input().split()))
	if z[0] == x or z[-1] == x:
		print(*reversed(z))
	else:
		print(-1)


def solve():
	n = int(input())
	A = [int(x) for x in input().split()]
	if A[0] == n:
		A = A[1:]
	elif A[-1] == n:
		A = A[:-1]
	else:
		print(-1)
		return
	A = A[::-1]
	print(*A, n)
t = int(input())
for _ in range(t):
	solve()


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]
inf = 4294967295
md = 998244353

def solve():
	n = II()
	aa = LI()
	if aa[0] == n:
		ans = [n] + aa[1:][::-1]
	elif aa[-1] == n:
		ans = aa[:-1][::-1] + [n]
	else:
		ans = [-1]
	print(*ans)
for testcase in range(II()):
	solve()