In fact, the problems E1 and E2 do not have much in common. You should probably think of them as two separate problems.

A permutation $p$ of size $n$ is given. A permutation of size $n$ is an array of size $n$ in which each integer from $1$ to $n$ occurs exactly once. For example, $[1, 4, 3, 2]$ and $[4, 2, 1, 3]$ are correct permutations while $[1, 2, 4]$ and $[1, 2, 2]$ are not.

Let us consider an empty deque (double-ended queue). A deque is a data structure that supports adding elements to both the beginning and the end. So, if there are elements $[1, 5, 2]$ currently in the deque, adding an element $4$ to the beginning will produce the sequence $[{4}, 1, 5, 2]$, and adding same element to the end will produce $[1, 5, 2, {4}]$.

The elements of the permutation are sequentially added to the initially empty deque, starting with $p_1$ and finishing with $p_n$. Before adding each element to the deque, you may choose whether to add it to the beginning or the end.

For example, if we consider a permutation $p = [3, 1, 2, 4]$, one of the possible sequences of actions looks like this:

$\quad$ 1.

add $3$ to the end of the deque:

deque has a sequence $[{3}]$ in it;

$\quad$ 2.

add $1$ to the beginning of the deque:

deque has a sequence $[{1}, 3]$ in it;

$\quad$ 3.

add $2$ to the end of the deque:

deque has a sequence $[1, 3, {2}]$ in it;

$\quad$ 4.

add $4$ to the end of the deque:

deque has a sequence $[1, 3, 2, {4}]$ in it;

Find the lexicographically smallest possible sequence of elements in the deque after the entire permutation has been processed.

A sequence $[x_1, x_2, \ldots, x_n]$ is lexicographically smaller than the sequence $[y_1, y_2, \ldots, y_n]$ if there exists such $i \leq n$ that $x_1 = y_1$, $x_2 = y_2$, $\ldots$, $x_{i - 1} = y_{i - 1}$ and $x_i < y_i$. In other words, if the sequences $x$ and $y$ have some (possibly empty) matching prefix, and the next element of the sequence $x$ is strictly smaller than the corresponding element of the sequence $y$. For example, the sequence $[1, 3, 2, 4]$ is smaller than the sequence $[1, 3, 4, 2]$ because after the two matching elements $[1, 3]$ in the start the first sequence has an element $2$ which is smaller than the corresponding element $4$ in the second sequence.


-----Input-----

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The next $2t$ lines contain descriptions of the test cases.

The first line of each test case description contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — permutation size. The second line of the description contains $n$ space-separated integers $p_i$ ($1 \le p_i \le n$; all $p_i$ are all unique) — elements of the permutation.

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


-----Output-----

Print $t$ lines, each line containing the answer to the corresponding test case. The answer to a test case should contain $n$ space-separated integer numbers — the elements of the lexicographically smallest permutation that is possible to find in the deque after executing the described algorithm.


-----Examples-----

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


-----Note-----

One of the ways to get a lexicographically smallest permutation $[1, 3, 2, 4]$ from the permutation $[3, 1, 2, 4]$ (the first sample test case) is described in the problem statement.

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Mathematics

Constructive algorithms


Solutions:
def solution_e1(l):
	result = []
	aux = [l[0]]
	tmpmin = l[0]
	for x in l[1:]:
		if x < tmpmin:
			tmpmin = x
			aux.append(x)
		else:
			result.append(x)
	return aux[::-1] + result
t = int(input())
for _ in range(t):
	try:
		ln = int(input())
		l = input()
		l = [int(x) for x in l.split(' ')]
		s = solution_e1(l)
		print(' '.join([str(c) for c in s]))
	except Exception as e:
		print(repr(e))


from sys import stdin
from collections import deque

def read_input():
	n = int(stdin.readline())
	p = list(map(int, stdin.readline().split()))
	return (n, p)

def solve(n, p):
	answer = deque()
	for pi in p:
		if len(answer) == 0 or pi < answer[0]:
			answer.appendleft(pi)
		else:
			answer.append(pi)
	return ' '.join(map(str, answer))

def main():
	t = int(stdin.readline())
	for _ in range(t):
		(n, p) = read_input()
		answer = solve(n, p)
		print(answer)
main()


from collections import deque
for __ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	Deque = deque([L[0]])
	L = L[1:]
	for x in L:
		if x <= Deque[0]:
			Deque.appendleft(x)
		else:
			Deque.append(x)
	print(' '.join((str(item) for item in Deque)))


from collections import deque

def solve():
	t = int(input())
	for i in range(t):
		n = int(input())
		m = [int(s) for s in input().split()]
		d = deque([m[0]])
		for j in range(1, n):
			if m[j] < d[0]:
				d.appendleft(m[j])
			else:
				d.append(m[j])
		print(' '.join((str(s) for s in d)))
solve()


from collections import deque
for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	final = deque()
	final.append(lis[0])
	for ele in lis[1:]:
		if final[0] > ele:
			final.appendleft(ele)
		else:
			final.append(ele)
	print(' '.join([str(i) for i in final]))


from collections import deque
import heapq
from math import sqrt
import operator
from operator import itemgetter
import sys
import copy
inf_var = 0
if inf_var == 1:
	inf = open('input.txt', 'r')
else:
	inf = sys.stdin
input = inf.readline

def read_one_int():
	return int(input().rstrip('\n'))

def read_one_float():
	return float(input().rstrip('\n'))

def read_list_of_ints():
	res = [int(val) for val in input().rstrip('\n').split()]
	return res

def read_list_of_ints_zero():
	return [int(val) - 1 for val in input().rstrip('\n').split()]

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

def main():
	tests = read_one_int()
	for _ in range(tests):
		n = read_one_int()
		elements = read_list_of_ints()
		right = []
		left = []
		left.append(elements[0])
		for i in range(1, n):
			if elements[i] < left[-1]:
				left.append(elements[i])
			else:
				right.append(elements[i])
		left.reverse()
		left.extend(right)
		print(' '.join(map(str, left)))
main()


import sys
from collections import deque

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

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

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

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

def solve(n, arr):
	queue = deque()
	queue.append(arr[0])
	for i in range(1, n):
		if arr[i] > queue[0]:
			queue.append(arr[i])
		else:
			queue.appendleft(arr[i])
	sys.stdout.write(' '.join(map(str, queue)) + '\n')
T = get_int()
while T:
	n = get_int()
	arr = get_list()
	solve(n, arr)
	T -= 1


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = deque()
	for num in a:
		if not d:
			d.append(num)
		elif num < d[0]:
			d.appendleft(num)
		else:
			d.append(num)
	print(' '.join(map(str, d)))


t = int(input())
from collections import deque
for _ in range(t):
	(n, line) = (int(input()), [int(x) for x in input().split()])
	res = deque()
	res.append(line[0])
	for el in line[1:]:
		if el < res[0]:
			res.appendleft(el)
		else:
			res.append(el)
	res = list(res)
	res = [str(x) for x in res]
	print(' '.join(res))


from collections import deque
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = deque([a[0]])
	if len(a) == 1:
		print(a[0])
		continue
	for k in range(1, len(a)):
		if a[k] <= d[0]:
			d.appendleft(a[k])
		else:
			d.append(a[k])
	e = list(d)
	print(' '.join([str(r) for r in e]))


from sys import stdin
from io import StringIO
from collections import deque
input = lambda : stdin.readline().strip()
linput = lambda : [*map(int, input().split())]
output = StringIO()

def lprint(*x):
	output.writelines((str(v) + ' ' for v in x))
	output.write('\n')

def main():
	n = int(input())
	a = linput()
	ans = deque()
	ans.append(a[0])
	for i in range(1, n):
		if a[i] < ans[0]:
			ans.appendleft(a[i])
		else:
			ans.append(a[i])
	lprint(*ans)
for _ in ' ' * int(input()):
	main()
print(output.getvalue())


t = int(input())
for _ in range(t):
	n = int(input())
	sss = input()
	p = list(map(int, sss.split(' ')))
	rez = [p[0]] * n
	left = 1
	right = 0
	for pi in p[1:]:
		if pi < rez[right]:
			right -= 1
			rez[right] = pi
		else:
			rez[left] = pi
			left += 1
	a = rez[left:]
	b = rez[:left]
	rrr = a + b
	print(' '.join(map(str, rrr)))


from collections import *
t = int(input())
for aslkdjlaskj in range(t):
	n = int(input())
	ipt = [int(i) for i in input().split()]
	dq = deque()
	dq.append(ipt[0])
	for i in range(1, n):
		if ipt[i] <= dq[0]:
			dq.appendleft(ipt[i])
		else:
			dq.append(ipt[i])
	print(' '.join([str(i) for i in dq]))


from collections import deque

def main():
	n = int(input())
	a = list(map(int, input().split()))
	d = deque([])
	d.append(a[0])
	for i in range(1, n):
		if a[i] <= d[0]:
			d.appendleft(a[i])
		else:
			d.append(a[i])
	print(' '.join([str(i) for i in d]))
t = int(input())
while t > 0:
	t -= 1
	main()


import sys
input = sys.stdin.readline
from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	d = deque()
	for i in range(n):
		if i == 0:
			d.append(p[i])
		elif p[i] < d[0]:
			d.appendleft(p[i])
		else:
			d.append(p[i])
	sys.stdout.write(' '.join(map(str, d)) + '\n')


import sys
from collections import deque

def rall():
	return sys.stdin.readlines()

def rl():
	return sys.stdin.readline().strip()

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
	return array
NT = int(rl())
for ti in range(NT):
	rl()
	array = list(map(int, rl().split(' ')))
	result = deque([array[0]])
	for v in array[1:]:
		if v < result[0]:
			result.appendleft(v)
		else:
			result.append(v)
	pra(list(result))


t = int(input())
from collections import deque
for xd in range(t):
	n = int(input())
	perm = [int(i) for i in input().split(' ')]
	d = deque()
	d.append(perm[0])
	for i in perm[1:]:
		if i < d[0]:
			d.appendleft(i)
		else:
			d.append(i)
	print(' '.join([str(i) for i in d]))


from collections import deque
x = int(input())
for i in range(x):
	y = int(input())
	z = input().split(' ')
	z = list(map(int, z))
	res = deque()
	res.append(z[0])
	for j in range(1, len(z)):
		if z[j] <= res[0]:
			res.appendleft(z[j])
		else:
			res.append(z[j])
	print(' '.join((str(obj) for obj in res)))


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	perm = list(map(int, input().split()))
	res = deque([perm[0]])
	for i in range(1, n):
		if perm[i] <= res[0]:
			res.appendleft(perm[i])
		else:
			res.append(perm[i])
	print(' '.join(map(str, res)))


from collections import deque
_ = int(input())
for __ in range(_):
	n = int(input())
	arr = list(map(int, input().split()))
	h = deque([arr[0]])
	if len(arr) == 1:
		print(arr[0])
		continue
	for x in range(1, len(arr)):
		if arr[x] <= h[0]:
			h.appendleft(arr[x])
		else:
			h.append(arr[x])
	l = list(h)
	print(' '.join([str(x) for x in l]))


from collections import deque
for _ in range(int(input())):
	n = int(input())
	p = [int(x) for x in input().split()]
	de = deque()
	for i in p:
		if len(de) == 0:
			de.append(i)
		elif i < de[0]:
			de.appendleft(i)
		else:
			de.append(i)
	print(' '.join(map(str, de)))


from collections import deque
t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	ans = deque()
	ans.append(p[0])
	for j in range(1, n):
		if p[j] < ans[0]:
			ans.appendleft(p[j])
		else:
			ans.append(p[j])
	print(' '.join((str(j) for j in ans)))


for x in range(int(input())):
	input()
	li = list(map(int, input().split()))
	l1 = []
	l2 = [li[0]]
	for i in range(1, len(li)):
		if li[i] < l2[-1]:
			l2.append(li[i])
		else:
			l1.append(li[i])
	l2.reverse()
	l0 = l2 + l1
	l0 = list(map(str, l0))
	print(' '.join(l0))


from collections import deque
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	queue = deque()
	queue.append(arr[0])
	for i in range(1, n):
		if arr[i] < queue[0]:
			queue.appendleft(arr[i])
		else:
			queue.append(arr[i])
	ans = ' '.join((str(i) for i in queue))
	print(ans)


t = int(input())
for tc in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	tail = [p[0]]
	head = [p[0]]
	for i in range(1, n):
		if p[i] < head[len(head) - 1]:
			head.append(p[i])
		else:
			tail.append(p[i])
	hsize = len(head)
	ans = []
	for i in range(hsize - 1, 0, -1):
		ans.append(head[i])
	for x in tail:
		ans.append(x)
	print(' '.join(map(str, ans)))


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(i) for i in input().split()]
	res = deque()
	for i in range(len(nums)):
		if len(res) == 0:
			res.append(nums[i])
		elif nums[i] <= res[0]:
			res.appendleft(nums[i])
		else:
			res.append(nums[i])
	print(' '.join([str(i) for i in res]))


from collections import deque
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = deque(arr)
	ans = deque()
	while arr:
		if not ans or (ans and int(ans[0]) < arr[0]):
			ans.append(str(arr.popleft()))
		else:
			ans.appendleft(str(arr.popleft()))
	print(' '.join(ans))


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	(*p,) = map(int, input().split())
	b = [0] * n
	bi = -1
	bv = int(1000000000.0)
	for i in range(n):
		if p[i] < bv:
			bv = p[i]
			bi = i
		b[i] = bi
	c = []
	i = n - 1
	while i >= 0:
		c.append(b[i])
		i = b[i] - 1
	c.reverse()
	j = 0
	d = []
	e = []
	for i in range(n):
		if j < len(c) and i == c[j]:
			d.append(str(p[i]))
			j += 1
		else:
			e.append(str(p[i]))
	d.reverse()
	print(' '.join(d + e))
for i in range(int(input())):
	solve()


from collections import deque

def solve(x):
	st = deque()
	for elem in x:
		if st and st[0] > elem:
			st.appendleft(elem)
		else:
			st.append(elem)
	return st
R = lambda : map(int, input().split())
(t,) = R()
while t > 0:
	t -= 1
	(n,) = R()
	x = list(R())
	print(*solve(x), sep=' ')


from collections import Counter, deque
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	n = int(input())
	arr = [int(char) for char in input().split()]
	q = deque([arr[0]])
	arr.pop(0)
	for a in arr:
		if a <= q[0]:
			q.appendleft(a)
		else:
			q.append(a)
	return list(q)
for _ in range(int(input())):
	print(*solve())


import sys
input = sys.stdin.readline
import collections
for _ in range(int(input())):
	n = int(input())
	p = [int(i) for i in input().split()]
	if n == 1:
		print('1')
		continue
	front = collections.deque()
	back = collections.deque()
	cur_min = 1
	seen = [False] * (n + 1)
	for i in range(n - 1, -1, -1):
		seen[p[i]] = True
		if p[i] != cur_min:
			back.append(p[i])
		else:
			front.append(p[i])
			while cur_min <= n and seen[cur_min]:
				cur_min += 1
	while back:
		front.append(back.pop())
	print(' '.join(map(str, front)))


from sys import stdin
from collections import deque

def func(arr):
	d = deque()
	for z in t:
		if not d or z < d[0]:
			d.appendleft(z)
		else:
			d.append(z)
	return d
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	t = list(map(int, stdin.readline().split()))
	print(*func(t))


from collections import deque
t = int(input())
for _ in range(t):

	def solve():
		n = int(input())
		lst = list(map(int, input().split()))
		q = deque()
		q.append(lst[0])
		for num in lst[1:]:
			if num < q[0]:
				q.appendleft(num)
			else:
				q.append(num)
		print(*q)
	solve()


from collections import deque
t = int(input())
for i in range(t):
	size = int(input().rstrip())
	numbers = input().rstrip().split(' ')
	result = deque([numbers[0]])
	final_result = ''
	for number in numbers[1:]:
		if int(number) > int(result[0]):
			result.append(number)
		else:
			result.appendleft(number)
	for j in result:
		final_result += f'{j} '
	print(f'{final_result}')


from collections import *

def solve():
	n = int(input())
	ll = list(map(int, input().split()))
	ans = deque()
	ans.append(ll[0])
	ll.pop(0)
	for i in ll:
		if ans[-1] > i and ans[0] > i:
			ans.appendleft(i)
		else:
			ans.append(i)
	return ans
t = int(input())
while t != 0:
	res = solve()
	print(*res)
	t -= 1


from collections import deque
for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	ans = deque()
	for i in lis:
		if ans and ans[0] > i:
			ans.appendleft(i)
		else:
			ans.append(i)
	print(*ans)


from _collections import deque
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = deque()
	b.append(a[0])
	for i in a[1:]:
		if i <= b[0]:
			b.appendleft(i)
		else:
			b.append(i)
	print(*b)


from collections import deque
t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	d = deque([p[0]])
	for w in p[1:]:
		if w < d[0]:
			d.appendleft(w)
		else:
			d.append(w)
	print(*d)


import collections

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	deque = collections.deque([])
	deque.append(arr[0])
	del arr[0]
	for i in arr:
		if i < deque[0]:
			deque.appendleft(i)
		else:
			deque.append(i)
	print(*deque, sep=' ')
for i in range(int(input())):
	solve()


from collections import deque
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	queue = deque([arr[0]])
	for i in arr[1:]:
		if i > queue[0]:
			queue.append(i)
		else:
			queue.appendleft(i)
	print(*queue)


from collections import Counter, deque
mod = 998244353

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	d = deque()
	curmin = 2000000
	curmax = -1
	for i in l:
		if i < curmin:
			curmin = i
			d.appendleft(i)
		else:
			d.append(i)
	print(*d)
t = int(input())
for _ in range(t):
	solve()


from collections import deque

def cf_744E(numbers):
	nums = deque()
	nums.append(numbers[0])
	for num in numbers[1:]:
		if num > nums[0]:
			nums.append(num)
		else:
			nums.appendleft(num)
	return list(nums)
for _ in range(int(input())):
	input()
	print(*cf_744E(list(map(int, input().split()))))


from collections import deque
t = int(input())
for i in range(t):
	_ = int(input())
	array = [int(el) for el in input().split()]
	answer = deque([])
	answer.append(array[0])
	for item in array[1:]:
		if item > answer[0]:
			answer.append(item)
		else:
			answer.appendleft(item)
	print(*answer, sep=' ')


from collections import deque
for t in range(int(input())):
	n = input()
	a = list(map(int, input().split()))
	q = deque()
	ans = []
	for c in a:
		if not q:
			q.append(c)
		elif q[0] > c:
			q.appendleft(c)
		else:
			q.append(c)
	ans = list(q)
	print(*ans)


import sys
input = sys.stdin.readline
from collections import deque
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	d = deque()
	for i in w:
		if d and d[0] > i:
			d.appendleft(i)
		else:
			d.append(i)
	print(*d)


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	l = [p[0]]
	r = []
	for w in p[1:]:
		if w < l[-1]:
			l.append(w)
		else:
			r.append(w)
	print(*l[::-1] + r)


import sys
import collections as cc
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
for tc in range(int(input())):
	(n,) = I()
	ar = I()
	temp = cc.deque()
	for i in ar:
		if not temp:
			temp.append(i)
		elif i < temp[0]:
			temp.appendleft(i)
		else:
			temp.append(i)
	print(*temp)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = []
	me = []
	for i in arr:
		if s == [] and me == []:
			me.append(i)
		elif s == []:
			if i < me[0]:
				s.append(i)
			else:
				me.append(i)
		elif i < s[-1]:
			s.append(i)
		else:
			me.append(i)
	print(*s[::-1] + me)


from collections import deque

def get_lexicographically_smallest_arr(arr):
	min_deque = deque()
	for number in arr:
		if len(min_deque) == 0:
			min_deque.append(number)
			continue
		if number < min_deque[0]:
			min_deque.appendleft(number)
		else:
			min_deque.append(number)
	return min_deque

def process_tests(test_count):
	for i in range(test_count):
		arr_len = int(input())
		arr = list(map(int, input().split()))
		print(*get_lexicographically_smallest_arr(arr), sep=' ')
test_count = int(input())
process_tests(test_count)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	q = deque([a[0]])
	for i in a[1:]:
		if i < q[0]:
			q.appendleft(i)
		else:
			q.append(i)
	print(*q)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = deque()
	for i in range(n):
		if not b or a[i] < b[0]:
			b.appendleft(a[i])
		else:
			b.append(a[i])
	print(*b)


from collections import *
for _ in range(int(input())):
	n = int(input())
	data = list(map(int, input().split()))
	ans = deque([data[0]])
	for i in range(1, n):
		if data[i] <= ans[0]:
			ans.insert(0, data[i])
		else:
			ans.append(data[i])
	print(*ans)


import collections
for _ in range(int(input())):
	input()
	p = list(map(int, input().split()))
	s = collections.deque()
	for x in p:
		if s and x < s[0]:
			s.appendleft(x)
		else:
			s.append(x)
	print(*s)


def solve(n, lst):
	(last, rev) = ([], [])
	if n == 1 or lst[0] == 1:
		print(*lst)
		return
	rev.append(lst[0])
	el = 1
	for i in range(1, n):
		if lst[i] > rev[el - 1]:
			last.append(lst[i])
			continue
		rev.append(lst[i])
		el += 1
	rev = rev[::-1]
	print(*rev + last)
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	solve(n, lst)


from collections import deque
for t in range(int(input())):
	N = int(input())
	ar = list(map(int, input().split()))
	D = deque()
	cm = None
	for i in ar:
		if not cm:
			D.append(i)
			cm = i
		elif i < cm:
			D.appendleft(i)
			cm = i
		else:
			D.append(i)
	print(*list(D))


import sys
import os
from math import ceil, floor, sqrt, gcd, factorial, log, log2
from io import BytesIO, IOBase
from collections import Counter, deque
from itertools import permutations, combinations
from bisect import bisect
from functools import reduce
inf = int(10000000000.0)
BUFSIZE = 8192
inp = lambda : int(input())
mp = lambda : map(int, input().split())
lst = lambda : list(map(int, input().split()))

def main():
	for _ in range(inp()):
		n = inp()
		p = lst()
		l = deque()
		l.append(p[0])
		for i in range(1, n):
			if p[i] < l[0]:
				l.appendleft(p[i])
			else:
				l.append(p[i])
		print(*l)
main()


from collections import deque
t = int(input())
for i in range(t):
	n = int(input())
	values = list(map(int, input().split()))
	q = deque([values[0]])
	ans = 0
	for d in values[1:]:
		if d <= q[0]:
			q.appendleft(d)
		elif d >= q[-1]:
			q.append(d)
		else:
			q.append(d)
	print(*q)


from collections import deque, defaultdict, Counter
cases = int(input())
for _ in range(cases):
	num = int(input())
	arr = list(map(int, input().split()))
	ans = deque()
	beg = arr[0]
	for n in arr:
		if n <= beg:
			ans.appendleft(n)
			beg = n
		else:
			ans.append(n)
	print(*list(ans))


from collections import deque
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = deque()
	l1.append(l[0])
	for i in range(1, n):
		if l[i] >= l1[0]:
			l1.append(l[i])
		else:
			l1.appendleft(l[i])
	print(*l1)


from collections import deque
test_case = int(input())
for i in range(test_case):
	permutation_size = int(input())
	elements = list(map(int, input().split()))
	first_element = deque([elements[0]])
	for j in elements[1:]:
		if j <= first_element[0]:
			first_element.appendleft(j)
		elif j >= first_element[-1]:
			first_element.append(j)
		else:
			first_element.append(j)
	print(*first_element)


from collections import deque
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	arr = deque([l[0]])
	val = l[0]
	for i in range(1, n):
		if l[i] < val:
			arr.appendleft(l[i])
			val = l[i]
		else:
			arr.append(l[i])
	print(*arr)


from collections import deque

def arrange(arr, n):
	d = deque()
	for i in range(n):
		if not d or arr[i] < d[0]:
			d.appendleft(arr[i])
		else:
			d.append(arr[i])
	return d
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(*arrange(a, n))


from _collections import deque
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = deque()
	for i in a:
		if l and l[0] > i:
			l.appendleft(i)
		else:
			l.append(i)
	print(*l)


import collections
num_test_cases = int(input())
for i in range(num_test_cases):
	permutation_size = int(input())
	elements = list(map(int, input().split()))
	deque = collections.deque([])
	deque.append(elements[0])
	del elements[0]
	for a in elements:
		if a < deque[0]:
			deque.insert(0, a)
		else:
			deque.append(a)
	print(*deque, sep=' ')


from collections import deque
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = deque([arr[0]])
	for i in range(1, len(arr)):
		if arr[i] > d[0]:
			d.append(arr[i])
		else:
			d.appendleft(arr[i])
	print(*d)


for _ in range(int(input())):
	n = int(input())
	a = [0] * (n * 2)
	(b, e) = (n, n)
	for x in map(int, input().split()):
		if b < e and x < a[b]:
			b -= 1
			a[b] = x
		else:
			a[e] = x
			e += 1
	print(*a[b:e])


def solve():
	n = int(input())
	v = [int(x) for x in input().split()]
	(le, ri) = ([], [])
	for el in v:
		if len(le) == 0 or el < le[-1]:
			le.append(el)
		else:
			ri.append(el)
	print(*le[::-1], *ri)
for _ in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	d = []
	e = [w[0]]
	for i in range(1, n):
		if w[i] > e[-1]:
			d.append(w[i])
		else:
			e.append(w[i])
	print(*e[::-1] + d)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	B = deque([])
	B.append(A[0])
	for i in range(1, n):
		if A[i] < B[0]:
			B.appendleft(A[i])
		else:
			B.append(A[i])
	print(*B)


from collections import deque
for _ in range(int(input())):
	x = int(input())
	z = deque()
	for i in list(map(int, input().split())):
		if z and z[0] > i:
			z.appendleft(i)
		else:
			z.append(i)
	print(*z)


import sys
from collections import deque

def input():
	return sys.stdin.readline().rstrip()
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	s = deque([lst[0]])
	min_v = lst[0]
	for num in lst[1:]:
		if num < min_v:
			min_v = num
			s.appendleft(num)
		else:
			s.append(num)
	print(*s, sep=' ')


import collections
t = int(input())
for _ in range(t):
	n = int(input())
	c = 10 ** 9
	a = list(map(int, input().split()))
	de = collections.deque([])
	for i in range(n):
		if c > a[i]:
			de.appendleft(a[i])
			c = a[i]
		else:
			de.append(a[i])
	print(*de)


from collections import deque
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	res = deque()
	res.append(l[0])
	for j in range(1, n):
		if l[j] < res[0]:
			res.appendleft(l[j])
		else:
			res.append(l[j])
	print(*res, sep=' ')