You are given a permutation $p_1, p_2, \ldots, p_n$ of length $n$. You have to choose two integers $l,r$ ($1 \le l \le r \le n$) and reverse the subsegment $[l,r]$ of the permutation. The permutation will become $p_1,p_2, \dots, p_{l-1},p_r,p_{r-1}, \dots, p_l,p_{r+1},p_{r+2}, \dots ,p_n$.

Find the lexicographically smallest permutation that can be obtained by performing exactly one reverse operation on the initial permutation.

Note that for two distinct permutations of equal length $a$ and $b$, $a$ is lexicographically smaller than $b$ if at the first position they differ, $a$ has the smaller element.

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 500$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 500$) — the length of the permutation.

The second line of each test case contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) — the elements of the permutation.


-----Output-----

For each test case print the lexicographically smallest permutation you can obtain.


-----Examples-----

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


-----Note-----

In the first test case, the permutation has length $1$, so the only possible segment is $[1,1]$. The resulting permutation is $[1]$.

In the second test case, we can obtain the identity permutation by reversing the segment $[1,2]$. The resulting permutation is $[1,2,3]$.

In the third test case, the best possible segment is $[2,3]$. The resulting permutation is $[1,2,4,3]$.

In the fourth test case, there is no lexicographically smaller permutation, so we can leave it unchanged by choosing the segment $[1,1]$. The resulting permutation is $[1,2,3,4,5]$.

Difficulty: EASY
Tags: Greedy algorithms

Mathematics

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(input().split())
	if n == 1:
		print(arr[0])
	else:
		for i in range(n):
			if arr[i] != str(i + 1):
				break
		ind = arr.index(str(i + 1))
		ss = arr[i:ind + 1]
		ss.reverse()
		arr = arr[:i] + ss + arr[ind + 1:]
		print(' '.join(arr))


def solve():
	n = int(input())
	arr = list(input().split())
	if n == 1:
		print(arr[0])
	else:
		for i in range(n):
			if arr[i] != str(i + 1):
				break
		ind = arr.index(str(i + 1))
		ss = arr[i:ind + 1]
		ss.reverse()
		arr = arr[:i] + ss + arr[ind + 1:]
		print(' '.join(arr))
for i in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	p = input().split()
	i = 0
	virus_start = None
	virus_end = None
	for i in range(n):
		if int(p[i]) != i + 1:
			virus_start = i
			virus_end = p.index(str(i + 1))
			break
	if virus_start is None:
		print(' '.join(p))
	else:
		print(' '.join(p[:virus_start]), ' '.join(p[virus_end:virus_start:-1]), p[virus_start], ' '.join(p[virus_end + 1:]))


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	input = sys.stdin.readline()
	myList = input.split()
	left = 0
	for i in range(n):
		if int(myList[i]) == i + 1:
			continue
		else:
			left = i
			break
	right = myList.index(str(left + 1))
	newList = myList[left:right + 1]
	newList.reverse()
	myList[left:right + 1] = newList
	print(' '.join(myList))


t = int(input())
while t:
	x = 0
	b = int(input())
	l = input().split(' ')
	for i in range(1, b + 1):
		if l[i - 1] != str(i):
			j = l.index(str(i))
			k = l[i - 1:j + 1]
			k.reverse()
			k = l[0:i - 1] + k + l[j + 1:b]
			x = 1
			break
	if x == 1:
		print(' '.join(k))
	else:
		print(' '.join(l))
	t -= 1


for _ in range(int(input())):
	n = int(input())
	p = [x for x in input().split()]
	for i in range(n):
		if p[i] != str(i + 1):
			r = p.index(str(i + 1)) + 1
			s = p[:i] + list(reversed(p[i:r])) + p[r:]
			print(' '.join(s))
			break
	else:
		print(' '.join(p))


def rev(m):
	for i in range(len(m)):
		if m[i] != i + 1:
			a = m.index(i + 1)
			return str(m[:i] + tuple(reversed(m[i:a + 1])) + m[a + 1:]).replace(',', ' ')[1:-1]
			break
	return str(m).replace(',', ' ')[1:-1]
test = int(input())
for i in range(test):
	n = int(input())
	m = tuple(map(int, input().split()))
	print(rev(m))


for _ in range(int(input())):
	n = int(input())
	perm = list(input().split())
	if n == 1:
		print('1')
	else:
		for x in range(1, n + 1):
			if str(x) != perm[x - 1]:
				break
		missind = perm.index(str(x))
		rev = perm[x - 1:missind + 1][::-1]
		final = perm[:x - 1] + rev + perm[missind + 1:]
		print(' '.join(final))


t = int(input())

def swap(P, l, r):
	for i in range(l, int((l + r) / 2) + 1):
		t = r - i + l
		(P[i], P[t]) = (P[t], P[i])
for _ in range(t):
	n = int(input())
	P = input().split()
	for i in range(n):
		s = str(i + 1)
		if P[i] != s:
			r = P.index(s)
			swap(P, i, r)
			break
	print(' '.join(P))


for i in range(int(input())):
	n = int(input())
	c = 0
	a = list(map(int, input().split()))
	for i in range(1, n + 1):
		if i != a[i - 1]:
			k = a.index(i)
			c = 1
			f = i - 1
			break
	if c == 1:
		if f == 0:
			t = a[k::-1]
		else:
			t = a[k:f - 1:-1]
		a = a[:f] + t + a[k + 1:]
		print(' '.join(list(map(str, a))))
	else:
		print(' '.join(list(map(str, a))))


def get_first_mistake_index(n, perm):
	for k in range(len(perm)):
		if perm[k] != k + 1:
			return k
	return -1

def correct(n, perm, first_mistake):
	left = first_mistake
	right = perm.index(first_mistake + 1)
	return perm[:left] + perm[left:right + 1][::-1] + perm[right + 1:]
t = int(input())
for _ in range(t):
	n = int(input())
	perm = [int(component) for component in input().split(' ')]
	first_mistake = get_first_mistake_index(n, perm)
	if first_mistake == -1:
		print(' '.join(map(str, perm)))
	else:
		print(' '.join(map(str, correct(n, perm, first_mistake))))


t = int(input())
for q in range(t):
	g = 1
	a = int(input())
	b = input().split()
	y = len(b)
	for i in range(len(b)):
		if str(g) != b[i]:
			break
		g = g + 1
	f = a
	if f == g or g > f:
		u = ' '.join(b)
		print(u)
		continue
	q = b.index(str(g))
	o = b[:g - 1] + b[g - 1:q + 1][::-1] + b[q + 1:]
	o1 = ' '.join(o)
	print(o1)


t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(str, input().split()))
	allnums = []
	visited = []
	for i in range(n):
		if p[i] != str(i + 1):
			break
	a = p.index(str(i + 1))
	newp = p.copy()
	newp[i:a + 1] = p[i:a + 1][::-1]
	print(' '.join(newp))


def reverse(arr, l, r):
	f_part = arr[:l]
	s_part = arr[l:r + 1][::-1]
	t_part = arr[r + 1:]
	arr_fin = f_part + s_part + t_part
	return arr_fin

def main():
	lng = int(input())
	arr = input().split()
	arr = list(map(int, arr))
	l = 0
	for i in range(lng):
		if arr[i] - 1 != i:
			l = i
			break
	r = arr.index(l + 1)
	ans = reverse(arr, l, r)
	if lng > 1:
		ans = ' '.join(map(str, ans))
	else:
		ans = ans[0]
	return ans
for i in range(int(input())):
	print(main())


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(len(arr)):
		if arr[i] != i + 1:
			ind = arr.index(i + 1)
			x = arr[i:ind + 1]
			x.reverse()
			arr[i:ind + 1] = x
			break
	print(' '.join(map(str, arr)))


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	for i in range(1, n + 1):
		if i == p[i - 1]:
			continue
		x = p.index(i, i - 1)
		p[i - 1:x + 1] = p[i - 1:x + 1][::-1]
		break
	print(' '.join(map(str, p)))


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	i = 0
	while i < n and p[i] == i + 1:
		i += 1
	if i == n:
		pass
	else:
		t = p.index(min(p[i:]))
		p = p[:i] + p[-n + t:-n + i - 1:-1] + p[t + 1:]
	print(' '.join(map(str, p)))


t = int(input())
for i in range(t):
	n = int(input())
	permutation = list(map(int, input().split(' ')))
	for index in range(len(permutation)):
		if permutation[index] == index + 1:
			pass
		elif index > 0:
			permutation = permutation[:index] + permutation[permutation.index(index + 1):index - 1:-1] + permutation[permutation.index(index + 1) + 1:]
			break
		else:
			permutation = permutation[:index] + permutation[permutation.index(index + 1)::-1] + permutation[permutation.index(index + 1) + 1:]
			break
	print(' '.join((str(k) for k in permutation)))


t = int(input())
for i in range(t):
	n = int(input())
	num = list(input().split())
	start = n - 1
	end = n
	for j in range(n):
		if str(j + 1) != num[j]:
			start = j
			break
	for j in range(start, n):
		if num[j] == str(start + 1):
			end = j
	num[start:end + 1] = reversed(num[start:end + 1])
	print(' '.join(num))


def solve(seq, length):
	need_permut = False
	i = 0
	for i in range(length):
		if seq[i] != i + 1:
			need_permut = True
			break
	if need_permut:
		target = seq.index(i + 1)
		seq = seq[:i] + seq[i:target + 1][::-1] + seq[target + 1:]
	return seq
n_case = int(input())
for _ in range(n_case):
	length = int(input())
	seq = list(map(int, input().split()))
	ans = solve(seq, length)
	print(' '.join(map(str, ans)))


for _ in range(int(input())):
	n = int(input())
	p = [i for i in input().split()]
	i = 0
	while i < n and p[i] == str(i + 1):
		i += 1
	t = n
	for j in range(i + 1, n):
		if p[j] == str(i + 1):
			t = j
			break
	if p[:i]:
		print(' '.join(p[:i]), end=' ')
	if p[i:t + 1]:
		print(' '.join(p[i:t + 1][::-1]), end=' ')
	print(' '.join(p[t + 1:]))


t = int(input())
for i in range(t):
	n = int(input())
	perm = list(map(int, input().split()))
	l = -1
	for j in range(n):
		if l == -1 and perm[j] != j + 1:
			l = j
	if l != -1:
		k = perm.index(l + 1)
		perm[l:k + 1] = perm[l:k + 1][::-1]
	print(' '.join((str(e) for e in perm)))


import math

def solve(a, n):
	(l, r) = (0, 0)
	for i in range(n):
		if a[i] != i + 1:
			l = i
			break
	for i in range(n):
		if a[i] == l + 1:
			r = i
			break
	for i in range(math.ceil((r - l) / 2)):
		(a[l + i], a[r - i]) = (a[r - i], a[l + i])
	print(' '.join(map(str, a)))
	return
t = int(input())
for i in range(1, t + 1):
	n = int(input())
	a = list(map(int, input().split()))
	solve(a, n)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sorted(l)
	start = -10
	for i in range(n):
		if l[i] != s[i]:
			end = i
			for j in range(i + 1, n):
				if l[j] == s[end]:
					start = j
					break
			break
	if start != -10:
		ans = l[:end] + l[end:start + 1][::-1] + l[start + 1:]
	else:
		ans = l
	print(' '.join(map(str, ans)))


def solve(a):
	i = 0
	while i < len(a) and a[i] == i + 1:
		i += 1
	if i != len(a):
		idx = a.index(i + 1)
		a = a[0:i] + a[i:idx + 1][::-1] + a[idx + 1:]
	return ' '.join(map(str, a))
out = []
t = int(input())
for case in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	out.append(solve(a))
print('\n'.join(out))


def solve():
	n = int(input())
	p = [int(i) for i in input().split()]
	for i in range(n):
		if p[i] == i + 1:
			continue
		else:
			for j in range(i + 1, n):
				if p[j] == i + 1:
					break
			break
	if i == n - 1:
		return p
	return p[:i] + p[i:j + 1][::-1] + p[j + 1:]
t = int(input())
for i in range(t):
	l = solve()
	print(' '.join([str(i) for i in l]))


n = int(input())
for x in range(n):
	l = int(input())
	arr = list(map(int, input().split()))
	flag = False
	imposter = 0
	for x in range(l):
		if arr[x] != x + 1:
			imposter = x + 1
			flag = True
			break
	if flag:
		index = 0
		for x in range(imposter - 1, l):
			if arr[x] == imposter:
				index = x
				break
		imposter -= 1
		str1 = ' '.join(list(map(str, arr[:imposter])))
		if imposter - 1 >= 0:
			str2 = ' '.join(list(map(str, arr[index:imposter - 1:-1])))
		else:
			str2 = ' '.join(list(map(str, arr[index::-1])))
		str3 = ' '.join(list(map(str, arr[index + 1:])))
		print((str1 + ' ' + str2 + ' ' + str3).strip())
	else:
		print(' '.join(list(map(str, arr))))


n = int(input())
new = []
ans = []
for i in range(n):
	new = []
	length = int(input())
	array = list(map(int, input().split()))
	count = 0
	for j in range(length):
		if array[j] == j + 1:
			continue
		num = array.index(j + 1)
		new = array[:j] + array[j:num + 1][::-1] + array[num + 1:]
		break
	if new == []:
		ans.append(array)
	else:
		ans.append(new)
for item in ans:
	print(' '.join(list(map(str, item))))


def Alert(a):
	result = []
	l = 0
	r = 0
	for _ in a:
		if a[l] == l + 1:
			l = l + 1
		else:
			break
	for _ in a:
		if a[r] != l + 1:
			r = r + 1
		else:
			break
	result = a[:l]
	result = result + a[l:r + 1][::-1]
	result = result + a[r + 1:]
	return result

def asd():
	a = input().split(' ')
	b = [int(e) for e in a]
	return b

def ACDC():
	n = asd()[0]
	for _ in range(n):
		d = asd()[0]
		t = Alert(asd())
		b = ' '.join([str(e) for e in t])
		print(b)
ACDC()


def rotate(values):
	left_value = 1
	while left_value < len(values):
		if left_value != values[left_value - 1]:
			break
		left_value += 1
	if left_value == len(values):
		return values
	right = values.index(left_value)
	left = left_value - 1
	while left < right:
		(values[left], values[right]) = (values[right], values[left])
		left += 1
		right -= 1
	return values

def print_values(values):
	print(' '.join(map(str, values)))
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	values = list(map(int, input().strip().split()))
	print_values(rotate(values))


def run(arr, n):
	for i in range(n):
		if arr[i] == i + 1:
			continue
		mi = -1
		for index in range(n):
			if arr[index] == i + 1:
				mi = index
				break
		a = min(i, mi)
		b = max(i, mi)
		arr[a:b + 1] = reversed(arr[a:b + 1])
		return arr
	return arr
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	res = run(arr, n)
	print(' '.join((str(i) for i in res)))


t = int(input())
for _ in range(t):
	found = False
	n = int(input())
	data = list(map(int, input().split()))
	exp = sorted(data)
	for i in range(n):
		if data[i] != exp[i]:
			j = data.index(exp[i])
			found = True
			break
	if found:
		data1 = data[:i] + data[i:j + 1][::-1] + data[j + 1:]
	else:
		data1 = data
	out = list(map(str, data1))
	print(' '.join(out))


for i in range(int(input())):
	input()
	nums = list(map(int, input().split()))
	c_n = list(sorted(nums))
	nums = list(map(str, nums))
	broken = False
	for p in range(len(c_n)):
		if str(c_n[p]) != nums[p]:
			x = nums.index(str(c_n[p]))
			print(' '.join(nums[:p] + list(reversed(nums[p:x + 1])) + nums[x + 1:]), end='\n')
			broken = True
			break
	if not broken:
		print(' '.join(nums), end='\n')


for _ in range(int(input())):
	n = int(input())
	permutation = list(map(int, input().split()))
	assert len(permutation) == n
	i = 1
	while i < len(permutation):
		if permutation[i - 1] != i:
			break
		i += 1
	l = i - 1
	minp = permutation[l]
	minp_index = l
	while i < len(permutation):
		if permutation[i] < minp:
			minp = permutation[i]
			minp_index = i
		i += 1
	permutation[l:minp_index + 1] = reversed(permutation[l:minp_index + 1])
	print(' '.join(map(str, permutation)))


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	ret = []
	x = -1
	for i in range(len(a)):
		if a[i] != i + 1:
			x = i
			break
		ret.append(i + 1)
	if x != -1:
		for i in range(x, len(a)):
			if a[i] == x + 1:
				y = i
				break
		for i in range(y, x - 1, -1):
			ret.append(a[i])
		for i in range(y + 1, len(a)):
			ret.append(a[i])
	print(' '.join(map(str, ret)))


def read_nums():
	return [int(x) for x in input().split()]

def solve():
	(n,) = read_nums()
	nums = read_nums()
	i = 0
	while i < len(nums) and nums[i] == i + 1:
		i += 1
	if i < len(nums):
		index = nums.index(i + 1)
		nums[i:index + 1] = nums[i:index + 1][::-1]
	print(' '.join(map(str, nums)))

def main():
	(t,) = read_nums()
	for _ in range(t):
		solve()
main()


import sys
from typing import List

def sol(perm: List[int]) -> List[int]:
	for idx in range(len(perm)):
		if idx + 1 != perm[idx]:
			break
	first_off = idx + 1
	for idx in range(idx + 1, len(perm)):
		if perm[idx] == first_off:
			break
	first_off_actual_pos = idx
	s = perm[:first_off - 1] + perm[first_off - 1:first_off_actual_pos + 1][::-1] + perm[first_off_actual_pos + 1:]
	return s

def main():
	inp = sys.stdin.readlines()
	rest = inp[1:]
	permutations = rest[1::2]
	permutations = [[int(num) for num in line.split()] for line in permutations]
	for perm in permutations:
		s = sol(perm)
		print(' '.join((str(a) for a in s)))
main()


def find(arr):
	left = -1
	right = -1
	for i in range(len(arr)):
		if left != -1:
			break
		if arr[i] != i + 1:
			left = i
			for j in range(i + 1, len(arr)):
				if arr[j] == i + 1:
					right = j
					break
	if left == -1:
		return arr
	two = arr[left:right + 1]
	two.reverse()
	if left == 0:
		if right == len(arr) - 1:
			return two
		else:
			return two + arr[right + 1:]
	elif right == len(arr) - 1:
		return arr[:left] + two
	else:
		return arr[:left] + two + arr[right + 1:]
num = int(input())
for i in range(num):
	n = input()
	arr = [int(x) for x in input().split()]
	a = find(arr)
	print(' '.join([str(x) for x in a]))


def main():
	n = int(input())
	for _ in range(n):
		t = int(input())
		nums = [int(s) for s in input().split()]
		i = 0
		while i < t and nums[i] == i + 1:
			i += 1
		if i == t:
			print(' '.join([str(num) for num in nums]))
		else:
			left = i
			while i < t and nums[i] != left + 1:
				i += 1
			right = i
			nums[:] = nums[:left] + nums[left:right + 1][::-1] + nums[right + 1:]
			print(' '.join([str(num) for num in nums]))
main()


numberOfTestCases = int(input())
for caseNumber in range(numberOfTestCases):
	lengthOfPermutation = int(input())
	permutationString = input()
	permutationList = [int(x) for x in permutationString.split(' ')]
	ticker = 1
	for x in permutationList:
		if ticker < x:
			break
		ticker += 1
	ind = ticker
	for i in range(ticker, lengthOfPermutation):
		if permutationList[i] == ticker:
			ind = i
	new = permutationList[0:ticker - 1] + permutationList[ind:ticker - 1:-1] + permutationList[ticker - 1:ticker] + permutationList[ind + 1:lengthOfPermutation]
	newStr = [str(x) for x in new]
	print(' '.join(newStr))


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	p = [int(x) for x in input().split(' ')]
	ll = -1
	rr = -1
	for j in range(n):
		if p[j] == j + 1:
			continue
		if ll > -1:
			if p[j] == ll:
				rr = j
				break
			continue
		ll = j + 1
	if rr > -1:
		res = p[:ll - 1]
		res = res + [p[x] for x in range(rr, ll - 2, -1)]
		res += p[rr + 1:]
	else:
		res = p
	print(' '.join([str(x) for x in res]))


import math

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

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

def yes(t):
	if t:
		return 'YES'
	return 'NO'

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

def solve():
	n = int(input())
	p = intlist()
	ind = 0
	if n == 1:
		return p[0]
	i = -1
	for j in range(n - 1):
		if p[j + 1] < p[j]:
			i = j
			break
	if i != -1:
		m = min(p[i + 1:])
		ma = i
		for j in range(i + 1):
			if p[j] > m:
				i = j
				break
		ind = p.index(m)
		p = p[:i] + p[ind:i:-1] + [p[i]] + p[ind + 1:]
	return printjoin(p)
t = input()
for tt in range(int(t)):
	print(solve())


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	for i in range(len(l)):
		if l[i] != i + 1:
			r = l.index(i + 1)
			temp = l[i:r + 1]
			temp.reverse()
			l = l[:i] + temp + l[r + 1:]
			break
	print(' '.join([str(x) for x in l]))


tests = int(input())
for i in range(tests):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	cnt = 0
	l = r = 0
	while cnt < len(arr):
		if arr[cnt] == cnt + 1:
			cnt += 1
		else:
			l = cnt
			break
	min1 = n + 1
	for i in range(l, len(arr)):
		if arr[i] < min1:
			min1 = arr[i]
			r = i
	while l < r:
		(arr[l], arr[r]) = (arr[r], arr[l])
		l += 1
		r -= 1
	for i in range(len(arr)):
		arr[i] = str(arr[i])
	print(' '.join(arr))


from re import L
T = int(input())
for _ in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	reverse_idx = -1
	for i in range(N):
		if arr[i] != i + 1 and reverse_idx == -1:
			reverse_idx = i
		elif arr[i] == reverse_idx + 1:
			(left, right) = (reverse_idx, i)
			while left < right:
				(arr[left], arr[right]) = (arr[right], arr[left])
				left += 1
				right -= 1
			break
	print(' '.join(list(map(str, arr))))


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	c = 0
	for j in range(n):
		if arr[j] != j + 1:
			idx = arr.index(j + 1)
			sub = arr[j:idx + 1]
			sub.reverse()
			new_arr = []
			new_arr = arr[:j] + sub + arr[idx + 1:len(arr)]
			new_arr = ' '.join([str(x) for x in new_arr])
			print(new_arr)
			c = 1
			break
	if c == 0:
		new_arr = ' '.join([str(x) for x in arr])
		print(new_arr)


t = int(input())

def q(l, n):
	l1 = []
	i = 0
	found = False
	while i < n and (not found):
		if l[i] == i + 1:
			l1.append(i + 1)
			i += 1
		elif l[i] > i + 1:
			index = l.index(i + 1)
			for j in range(index, i - 1, -1):
				l1.append(l[j])
			for k in range(index + 1, n):
				l1.append(l[k])
			i = n
			return l1
	return l1

def h(l):
	l2 = list(map(str, l))
	return ' '.join(l2)
for i in range(t):
	n = int(input())
	j = input().split()
	l = list(map(int, j))
	print(h(q(l, n)))


def least_permutation(A, n):
	l = 0
	r = None
	for i in range(n - 1):
		if A[i + 1] < A[i]:
			if r == None:
				r = i + 1
			elif A[i + 1] < A[r]:
				r = i + 1
	if r != None:
		for i in range(n):
			if A[i] > A[r]:
				l = i
				break
		while l < r:
			A[l] = A[l] + A[r]
			A[r] = A[l] - A[r]
			A[l] = A[l] - A[r]
			l += 1
			r -= 1
	return A
t = int(input())
for i in range(t):
	n = int(input())
	permutation = list((int(i) for i in input().strip().split()))
	ans = least_permutation(permutation, n)
	print(' '.join(map(str, ans)))


import math
import sys
import itertools
import fractions
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
GAP = 2
for t in [wtf[i:i + GAP] for i in range(1, len(wtf), GAP)]:
	n = int(t[0])
	A = list(map(int, t[1].split()))
	Ak = [i for i in range(n)]
	Aks = [i for i in sorted(range(n), key=lambda k: A[k])]
	(r, l) = (-1, -1)
	f = False
	for i in range(n):
		if Ak[i] != Aks[i]:
			r = Aks[i]
			l = i
			f = True
			break
	if f is True:
		A[l:r + 1] = reversed(A[l:r + 1])
	print(' '.join(map(str, A)))


nbTest = int(input())

def reverse(str, i, j):
	tmp = str[0:i]
	tmp2 = str[j + 1:len(str)]
	tmp3 = str[i:j + 1][::-1]
	return tmp + tmp3 + tmp2
for ahah in range(nbTest):
	nbElem = int(input())
	elems = [int(i) for i in input().split()]
	for i in range(nbElem):
		if i + 1 != elems[i]:
			index = elems.index(i + 1)
			elems = reverse(elems, i, index)
			break
	for i in range(nbElem):
		elems[i] = str(elems[i])
	print(' '.join(elems))


from audioop import reverse
ans = []
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(srch, start, last) = (-1, -1, -1)
	for i in range(len(arr)):
		if i + 1 != arr[i]:
			srch = i + 1
			start = i
			break
	if srch == -1:
		ans.append(' '.join((str(x) for x in arr)))
	else:
		for i in range(len(arr)):
			if arr[i] == srch:
				last = i
				break
		arr_copy = arr[start:last + 1]
		arr_copy.reverse()
		arr[start:last + 1] = arr_copy
		ans.append(' '.join((str(x) for x in arr)))
for x in ans:
	print(x)


def lis_str(lis):
	string = ''
	for x in lis:
		string += x + ' '
	return string[:-1]
t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	lis_input = input().split()
	l = -1
	r = -1
	for (i, x) in enumerate(lis_input):
		if i + 1 < int(x):
			l = i
			break
	if l != -1:
		for i in range(l, n):
			if int(lis_input[i]) == l + 1:
				r = i
	if l != -1 and r != -1:
		part_1 = lis_input[:l]
		part_2 = lis_input[l:r + 1]
		part_3 = lis_input[r + 1:]
		lis_fin = part_1 + part_2[::-1] + part_3
		print(lis_str(lis_fin))
	else:
		print(lis_str(lis_input))


from typing import List

def get_minimum_permutation(arr: List) -> List:
	arr_length = len(arr)
	if arr_length < 2:
		return arr
	x = arr.copy()
	x.sort()
	swap_index = [-1, -1]
	for i in range(arr_length):
		if arr[i] != x[i]:
			swap_index[0] = i
			break
	if swap_index[0] == -1:
		return arr
	need_to_replace = min(arr[i:])
	for j in range(arr_length - 1, i - 1, -1):
		if arr[j] == need_to_replace:
			swap_index[1] = j
			break
	if swap_index[0] == swap_index[1]:
		return arr
	(i, j) = (swap_index[0], swap_index[1])
	while i < j:
		temp = arr[j]
		arr[j] = arr[i]
		arr[i] = temp
		i += 1
		j -= 1
	return arr
n = int(input().strip())
need_to_process_lists = []
for input_list in range(n):
	input()
	elements = [int(x) for x in input().strip().split(' ')]
	need_to_process_lists.append(elements)
for process_list in need_to_process_lists:
	did_processed_list = get_minimum_permutation(process_list)
	print(' '.join((str(key) for key in did_processed_list)))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ix = -1
	num = 0
	for i in range(1, n + 1):
		if i != l[i - 1]:
			ix = i - 1
			num = i
			break
	if ix == -1:
		print(' '.join([str(x) for x in l]))
		continue
	ni = l.index(num)
	beg = l[:max(ix, 0)]
	ll = l[ix:ni + 1]
	ll.reverse()
	print(' '.join([str(x) for x in beg + ll]), end=' ')
	for i in range(ni + 1, n):
		print(l[i], end=' ')
	print()


for z in range(int(input())):
	input()
	nos = list(map(int, input().split()))
	c_n = list(sorted(nos))
	nos = list(map(str, nos))
	broken = False
	for z in range(len(c_n)):
		if str(c_n[z]) != nos[z]:
			x = nos.index(str(c_n[z]))
			print(' '.join(nos[:z] + list(reversed(nos[z:x + 1])) + nos[x + 1:]), end='\n')
			broken = True
			break
	if not broken:
		print(' '.join(nos), end='\n')


n = int(input())
for i in range(n):
	a = int(input())
	num = list(map(int, input().split()))
	new_num = sorted(num)
	start = 0
	end = 0
	for y in range(len(num)):
		if num[y] != new_num[y]:
			start = y
			break
	for x in range(len(num)):
		if num[x] == new_num[start]:
			end = x
			break
	num[start:end + 1] = reversed(num[start:end + 1])
	print(' '.join([str(w) for w in num]))


num_cases = int(input())
for _ in range(num_cases):
	perm_len = int(input())
	arr = [int(each) for each in input().split(' ')]
	is_sorted = True
	for (a, b, i) in zip(arr, sorted(arr), range(perm_len)):
		if a == b:
			continue
		is_sorted = False
		a = a
		b = b
		i = i
		break
	if is_sorted:
		print(' '.join([str(each) for each in arr]))
		continue
	indices = []
	for (each, idx) in zip(arr, range(perm_len)):
		if each == b:
			indices.append((idx, idx))
	stack1 = indices
	stack2 = []
	while True:
		if len(stack1) == 0:
			break
		min_val = arr[stack1[0][0]]
		if len(stack1) == 1:
			(left, right) = stack1[0]
			inner = arr[i:right + 1]
			inner = list(reversed(inner))
			new_list = arr[0:i] + inner + arr[right + 1:]
			print(' '.join([str(each) for each in new_list]))
			break
		for (each, right) in stack1:
			if each == i:
				inner = arr[i:right + 1]
				inner = list(reversed(inner))
				new_list = arr[0:i] + inner + arr[right + 1:]
				print(' '.join([str(z) for z in new_list]))
				break
			val = arr[each]
			if val < min_val:
				stack2 = []
				stack2.append((each - 1, right))
				min_val = val
			elif val == min_val:
				stack2.append((each - 1, right))
		stack1 = stack2
		stack2 = []


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	m = [None] * n
	m[-1] = a[-1]
	for i in range(n - 2, -1, -1):
		m[i] = min(m[i + 1], a[i])
	r = a
	for i in range(n):
		if a[i] != m[i]:
			for j in range(i, n):
				if a[j] == m[i]:
					b = a[:i] + a[j:i - 1 if i > 0 else None:-1] + a[j + 1:]
					r = min(r, b)
			break
	print(' '.join(map(str, r)))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


t = int(input())

def search(k, p):
	for (l, x) in enumerate(p):
		if p[l] == k:
			return l
for i in range(t):
	n = int(input())
	p = input()
	p = p.split(' ')
	p = [int(x) for x in p]
	r = 0
	l = 0
	for (k, x) in enumerate(p):
		if p[k] != k + 1:
			l = search(k + 1, p)
			r = k
			break
	section = p[r:l + 1]
	section.reverse()
	p[r:l + 1] = section
	print(' '.join((str(x) for x in p)))


T = int(input())

def lst_to_string(lst):
	s = ''
	for i in lst:
		s += str(i) + ' '
	s = s[:-1]
	return s

def reverse_list(list_name, st_index, end_index):
	if st_index == 0:
		lst = list_name[end_index::-1] + list_name[end_index + 1:]
	else:
		lst = list_name[:st_index] + list_name[end_index:st_index - 1:-1] + list_name[end_index + 1:]
	return lst

def main(obj):
	x = obj.line
	l = obj.l
	if l == 1 or x == sorted(x):
		return lst_to_string(x)
	start = 0
	for i in range(l):
		if x[i] > i + 1:
			start = i
			break
	end = x.index(min(x[start:]))
	return lst_to_string(reverse_list(x, start, end))

class case:

	def __init__(self, line):
		self.line = [int(i) for i in line.split()]
		self.l = len(self.line)
cases = []
for i in range(T):
	l = int(input())
	line = input()
	cases.append(case(line))
for i in range(T):
	print(main(cases[i]))


def solve(n, arr):
	if sorted(arr) == arr:
		s = ''.join((str(x) + ' ' for x in arr))
		return s.strip()
	ar2 = list(arr)
	ar2.sort()
	for i in range(n):
		if ar2[i] == arr[i]:
			continue
		el = arr.index(min(arr[i:]))
		new_ar = arr[:i] + arr[i:el + 1][::-1] + arr[el + 1:]
		s = ''.join((str(x) + ' ' for x in new_ar))
		return s.strip()
n = int(input())
for i in range(n):
	n2 = int(input())
	l = input()
	l = [int(x) for x in l.split(' ')]
	print(solve(n2, l))


import sys
T = int(sys.stdin.readline())
for t in range(T):
	n = int(sys.stdin.readline())
	a = [int(x) for x in sys.stdin.readline().split(' ')]
	i = 1
	while i <= n:
		if a[i - 1] != i:
			break
		i += 1
	if i == n + 1:
		print(' '.join(map(str, a)))
		continue
	j = i
	while j <= n:
		if a[j - 1] == i:
			break
		j += 1
	b = a[:i - 1]
	for k in range(i - 1, j):
		b.append(a[i + j - k - 2])
	b += a[j:]
	print(' '.join(map(str, b)))


T = int(input())
for t in range(T):
	N = int(input())
	perm = list(map(int, input().split()))
	i = 0
	while i + 1 == perm[i] and i != len(perm) - 1:
		i += 1
	if i == len(perm) - 1:
		print(' '.join(list(map(str, perm))))
	elif i == 0:
		j = 1
		while perm[j] != 1 and j != len(perm) - 1:
			j += 1
		chunk = list(reversed(perm[:j + 1]))
		new = chunk + perm[j + 1:]
		print(' '.join(list(map(str, new))))
	else:
		k = i
		while k != len(perm) - 1 and perm[k] != perm[i - 1] + 1:
			k += 1
		chunk = list(reversed(perm[i:k + 1]))
		new = perm[:i] + chunk + perm[k + 1:]
		print(' '.join(list(map(str, new))))


t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	first_wrong = 0
	while first_wrong < n and p[first_wrong] == first_wrong + 1:
		first_wrong += 1
	if first_wrong < n:
		needed_index = first_wrong
		while p[needed_index] != first_wrong + 1:
			needed_index += 1
		p = p[:first_wrong] + p[first_wrong:needed_index + 1][::-1] + p[needed_index + 1:]
	ans = ''
	for num in p:
		ans += f'{num} '
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(XXX) for XXX in input().split()]
	res = ''.join([XXX for XXX in str(arr).split(',') if len(XXX) > 0])
	for i in range(n):
		if arr[i] != i + 1:
			p = arr.index(i + 1)
			reversedPrefix = arr[i:p + 1][::-1]
			arr = arr[:i] + reversedPrefix + arr[p + 1:]
			res = ''.join([XXX for XXX in str(arr).split(',') if len(XXX) > 0])
			break
	res = res[1:len(res) - 1]
	print(res)


def minPermutation(n, data):
	ans = data
	res = None
	min_v = []
	for i in range(n):
		pos = n - i - 1
		if len(min_v) == 0:
			min_v.append((data[pos], pos))
			continue
		if data[pos] < min_v[-1][0]:
			min_v.append((data[pos], pos))
		else:
			min_v.append(min_v[-1])
	min_v = min_v[::-1]
	for i in range(n):
		if data[i] > min_v[i][0]:
			ans = data[:i] + data[i:min_v[i][1] + 1][::-1] + data[min_v[i][1] + 1:]
			break
	return ans

def run():
	t = int(input())
	for i in range(t):
		n = int(input())
		data = input().split(' ')
		data = [int(x) for x in data]
		ans = minPermutation(n, data)
		print(' '.join([str(x) for x in ans]))
run()


import sys

def _input_iter():
	for line in sys.stdin:
		for part in line.strip().split(' '):
			stripped = part.strip()
			if stripped:
				yield stripped
stream = _input_iter()

def read_int():
	return int(next(stream))

def read_str():
	return next(stream)

def run():
	n = read_int()
	permutation = []
	for i in range(n):
		permutation.append(read_int())
	(l, r) = (-1, -1)
	for i in range(len(permutation)):
		if i + 1 != permutation[i] and l == -1:
			l = i
		if permutation[i] == l + 1 and r == -1:
			r = i + 1
	permutation[l:r] = list(reversed(permutation[l:r]))
	print(' '.join((str(i) for i in permutation)))
test_cases = read_int()
for _ in range(test_cases):
	run()


def solveA(a):
	a_with_positions = []
	for (index, value) in enumerate(a):
		a_with_positions.append([value, index])
	a_with_positions = sorted(a_with_positions, key=lambda x: x[0])
	for (index, value) in enumerate(a):
		if value == a_with_positions[index][0]:
			continue
		else:
			return swap(a, index, a_with_positions[index][1])
	return a

def swap(a, l, r):
	while l < r:
		aux = a[l]
		a[l] = a[r]
		a[r] = aux
		l += 1
		r -= 1
	return a
num_tests = int(input().split()[0])
for t in range(num_tests):
	n = int(input().split()[0])
	a = [int(x) for x in input().split()]
	result = solveA(a)
	print(' '.join([str(val) for val in result]))


tc = int(input())
for i in range(tc):
	x = int(input())
	z = list(map(int, input().split()))
	y = z.copy()
	y.insert(0, 0)
	list1 = []
	for i in range(1, x):
		if y[i] - y[i - 1] != 1:
			a = z[y.index(y[i]) - 1:y.index(y[i - 1] + 1)]
			g = z[:i - 1] + a[::-1] + z[y.index(y[i - 1] + 1):]
			str1 = ''
			for i in range(len(g)):
				str1 += str(g[i]) + ' '
			print(str1)
			break
		else:
			continue
	else:
		str1 = ''
		for i in range(len(z)):
			str1 += str(z[i]) + ' '
		print(str1)


loopcount = int(input())
for loop in range(loopcount):
	a = int(input())
	x = input()
	x = x.split(' ')
	x = list(map(int, x))
	y = x.copy()
	y.sort()
	output = []
	z = []
	ok = True
	i = 0
	while i < a:
		if x[i] != y[i] and ok:
			global swap
			swap = y[i]
			for j in range(i, a):
				z.append(x[j])
				if x[j] == swap:
					i = j
					break
			z.reverse()
			ok = False
			output += z
		else:
			output.append(x[i])
		i += 1
	string_ints = [str(int) for int in output]
	print(' '.join(string_ints))


t = int(input())
for _ in range(t):
	n = int(input())
	p = input().split()
	runningMin = [i for i in range(n)]
	runningMin[n - 1] = n - 1
	for i in range(n - 2, -1, -1):
		if int(p[i]) < int(p[runningMin[i + 1]]):
			runningMin[i] = i
		else:
			runningMin[i] = runningMin[i + 1]
	for i in range(n):
		if runningMin[i] != i:
			p[i:runningMin[i] + 1] = reversed(p[i:runningMin[i] + 1])
			break
	print(' '.join(p))


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	list2 = []
	flag1 = 0
	j = 0
	num = 0
	s = ''
	for i in range(0, len(list1)):
		if list1[i] != i + 1:
			flag1 = 1
			num = i + 1
			j = i
			break
		else:
			s += str(list1[i]) + ' '
	if flag1 == 1:
		for j in range(i, len(list1)):
			if list1[j] == num:
				break
		k = j
		for k in range(j, i - 1, -1):
			s += str(list1[k]) + ' '
		k = j + 1
		for k in range(j + 1, len(list1)):
			s += str(list1[k]) + ' '
	print(s)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	nth = 0
	for i in range(n):
		if a[i] != i + 1:
			nth = a.index(i + 1)
			print(*a[:i] + a[i:nth + 1][::-1] + a[nth + 1:])
			return
	print(*a)
tst = int(input())
while tst:
	solve()
	tst -= 1


for s in [*open(0)][2::2]:
	a = [*map(int, s.split()), 0]
	i = 0
	while a[i] == i + 1:
		i += 1
	if a[i]:
		j = a.index(i + 1) + 1
		a[i:j] = a[i:j][::-1]
	print(*a[:-1])


for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	for i in range(len(li)):
		if li[i] != i + 1:
			index = li.index(i + 1)
			li[i:index + 1] = li[i:index + 1][::-1]
			break
	print(*li)


for case in range(int(input())):
	length = int(input())
	line = list(map(int, input().split()))
	for i in range(length):
		if line[i] != i + 1:
			number = line.index(i + 1)
			line[i:number + 1] = reversed(line[i:number + 1])
			break
	print(*line)


t = int(input())
for _ in range(t):
	l = int(input())
	a = list(map(int, input().split()))
	n = 1
	i = 0
	br = 0
	ln = []
	for d in a:
		if n == d:
			n = n + 1
		else:
			br = 1
			break
	if br == 0:
		print(*a)
	else:
		i = n - 1
		i2 = a.index(n)
		m = a[i:i2 + 1]
		m = m[::-1]
		ln = ln + a[:i] + m + a[i2 + 1:]
		print(*ln)


t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	for i in range(n):
		if p[i] != i + 1:
			break
	j = p.index(i + 1)
	p[i:j + 1] = p[i:j + 1][::-1]
	print(*p)


import sys
t = int(sys.stdin.readline())
for k in range(0, t):
	n = int(sys.stdin.readline())
	p = list(map(int, sys.stdin.readline().split()))
	L = 0
	R = 0
	for i in range(0, n):
		if p[i] > i + 1:
			L = i + 1
			break
	if L == 0:
		pp = p.copy()
	elif L == 1:
		R = p.index(L)
		pp = p[R:0:-1]
		pp.extend(p[0:1])
		pp.extend(p[R + 1:])
	else:
		R = p.index(L)
		pp = p[0:L - 1]
		pp.extend(p[R:L - 2:-1])
		pp.extend(p[R + 1:])
	for i in range(0, n):
		sys.stdout.write(str(pp[i]) + ' ')
	sys.stdout.write('\n')


from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
sqrt = math.sqrt

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

def LF():
	return list(map(float, input().split()))

def LI_():
	return list(map(lambda x: int(x) - 1, input().split()))

def II():
	return int(input())

def IF():
	return float(input())

def S():
	return input().rstrip()

def LS():
	return S().split()

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = 10000000000.0

def solve():
	t = II()
	for _ in range(t):
		n = II()
		p = LI()
		l = -1
		r = -1
		for i in range(n):
			if i + 1 != p[i]:
				for j in range(i + 1, n):
					if i + 1 == p[j]:
						l = i
						r = j + 1
						break
				break
		if l == -1:
			print(*p)
		else:
			ans = p[:l] + list(reversed(p[l:r])) + p[r:]
			print(*ans)
	return
solve()


def func():
	n = int(input())
	l = list(map(int, input().split()))
	req = -1
	for i in range(n):
		if l[i] != i + 1:
			req = i + 1
			break
	if req == -1:
		print(*l)
		return
	idx = l.index(req)
	l = l[:req - 1] + l[req - 1:idx + 1][::-1] + l[idx + 1:]
	print(*l)
t = int(input())
for i in range(t):
	func()


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split(' ')))
	for i in range(n):
		if nums[i] != i + 1:
			idx = nums.index(i + 1)
			nums[i:idx + 1] = nums[i:idx + 1][::-1]
			break
	print(*nums)


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	(left, right) = (-1, -1)
	for i in range(len(arr)):
		if arr[i] != i + 1:
			left = i
			break
	else:
		return arr
	for i in range(i + 1, len(arr)):
		if arr[i] == left + 1:
			right = i
			break
	length = right - left + 1
	for i in range(int(length / 2)):
		(arr[left + i], arr[right - i]) = (arr[right - i], arr[left + i])
	return arr

def main():
	res = []
	t = int(input())
	for _ in range(t):
		res.append(solve())
	for i in range(len(res)):
		print(*res[i])
main()


t = int(input())
for j in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	a = 0
	b = 0
	for i in range(n):
		if s[i] != i + 1:
			a = i
			b = s.index(i + 1)
			break
	s[a:b + 1] = s[b:a:-1] + s[a:a + 1]
	print(*s)


for i in range(int(input())):
	n = int(input())
	a = [*map(int, input().split()), 0]
	i = 0
	while a[i] == i + 1:
		i = i + 1
	j = 0
	if a[i]:
		j = a.index(i + 1) + 1
	a[i:j] = a[i:j][::-1]
	print(*a[:-1])


t = int(input())
for zz in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	for i in range(n):
		if l[i] == i + 1:
			continue
		else:
			k = i
			break
	p = l.index(k + 1)
	l1 = l[k:p + 1]
	l1 = l1[::-1]
	print(*l[:k] + l1 + l[p + 1:])


from sys import stdin
from math import log, floor, ceil, gcd
from collections import defaultdict as dd
input = stdin.readline
inp = lambda : int(stdin.readline())
rs = lambda : stdin.readline().strip()

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		n = inp()
		p = ra(int)
		for i in range(n):
			if p[i] != i + 1:
				x = p.index(i + 1)
				p[i:x + 1] = p[i:x + 1][::-1]
				break
		print(*p)
main()