Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

You are given a sequence $A_{1}, A_{2}, \ldots, A_{N}$ of distinct integers. While the sequence contains at least three elements, look at its first three elements, find the median among these elements and delete it. What will the final sequence be?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing $K$ space-separated integers, where $K$ is the length of the final sequence. For each valid $i$, the $i$-th of these integers should be the $i$-th element of the final sequence.

------  Constraints ------
$1 ≤ T ≤ 74$
$3 ≤ N ≤ 19$
$1 ≤ A_{i} ≤ 109$ for each valid $i$

----- Sample Input 1 ------ 
2
3
2 5 3
10
38 9 102 10 96 7 46 28 88 13
----- Sample Output 1 ------ 
2 5 
102 7
----- explanation 1 ------ 
Example case 1: We remove the element $3$ because it is the median of $(2, 5, 3)$. The final sequence is $(2, 5)$.

Source: codechef | Difficulty: EASY
Tags: Complete search

Constructive algorithms

Ad-hoc


Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a.index(max(a)) > a.index(min(a)):
		print(min(a), max(a))
	else:
		print(max(a), min(a))


from statistics import median
goals = int(input())
for distractions in range(goals):
	wife = int(input())
	life = list(map(int, input().split()))
	while len(life) > 2:
		life.remove(median(life[:3]))
	print(*life)


from statistics import median
for i in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	while len(l) > 2:
		l.remove(median(l[:3]))
	print(*l)


t = int(input())
for _ in range(t):
	n = int(input())
	integers = list(map(int, input().split()))
	if integers.index(max(integers)) < integers.index(min(integers)):
		print(max(integers), min(integers))
	else:
		print(min(integers), max(integers))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = a.index(min(a))
	d = a.index(max(a))
	if c < d:
		print(min(a), ' ', max(a))
	else:
		print(max(a), ' ', min(a))


for _ in range(int(input())):
	n = int(input())
	a = tuple(zip(map(int, input().split()), range(n)))
	minmax = sorted((min(a), max(a)), key=lambda x: x[1])
	print(*[i for (i, j) in minmax])


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	mini = min(l)
	maxi = max(l)
	if l.index(mini) > l.index(maxi):
		print(maxi, mini)
	else:
		print(mini, maxi)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	a = max(lis)
	b = min(lis)
	for i in lis:
		if i == a:
			print(a, b)
			break
		elif i == b:
			print(b, a)
			break


try:
	for _ in range(int(input())):
		N = int(input())
		L = list(map(int, input().split()))
		while len(L) > 2:
			l = L[:3]
			l.remove(min(l))
			L.remove(min(l))
		print(*L)
except:
	pass


for test_case in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	while len(a) != 2:
		a1 = sorted([a[1], a[0], a[2]])[1]
		if a[0] == a1:
			a.remove(a[0])
		elif a[1] == a1:
			a.remove(a[1])
		else:
			a.remove(a[2])
	print(*a, sep=' ')


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	mi = min(b)
	ma = max(b)
	i = b.index(mi)
	j = b.index(ma)
	if i > j:
		print(ma, ' ', mi)
	else:
		print(mi, ' ', ma)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	mini = min(l)
	maxi = max(l)
	if l.index(mini) < l.index(maxi):
		print(mini, maxi)
	else:
		print(maxi, mini)


t = int(input())
while t:
	N = int(input())
	A = list(map(int, input().split()))
	i = A.index(min(A))
	j = A.index(max(A))
	if i > j:
		print(max(A), min(A))
	else:
		print(min(A), max(A))
	t = t - 1


for i in range(int(input())):
	N = int(input())
	li = list(map(int, input().split()))
	mins = min(li)
	maxs = max(li)
	if li.index(mins) > li.index(maxs):
		print(maxs, mins)
	else:
		print(mins, maxs)


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	c = A.index(min(A))
	d = A.index(max(A))
	if c < d:
		print(min(A), ' ', max(A))
	else:
		print(max(A), ' ', min(A))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(me, mi) = (max(l), min(l))
	if l.index(mi) > l.index(me):
		print(me, mi)
	else:
		print(mi, me)


import statistics
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	a = min(A)
	b = max(A)
	for i in A:
		if i == a or i == b:
			print(i, end=' ')
	print()


def median(a, b, c):
	lst = []
	lst.append(a)
	lst.append(b)
	lst.append(c)
	lst = sorted(lst)
	return lst[1]
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	while len(lst) > 2:
		m = median(lst[0], lst[1], lst[2])
		lst.remove(m)
	print(lst[0], lst[1], sep=' ')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	h = a.index(min(a))
	g = a.index(max(a))
	if h < g:
		print(min(a), max(a))
	else:
		print(max(a), min(a))


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = min(a)
	c = max(a)
	for j in a:
		if b == j:
			print(b, c)
			break
		elif c == j:
			print(c, b)
			break


for t in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split(' ')))
	a = min(nums)
	b = max(nums)
	c = nums.index(a)
	d = nums.index(b)
	if c < d:
		print(a, b)
	else:
		print(b, a)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = max(a)
	c = min(a)
	for i in a:
		if i == b or i == c:
			print(i, end=' ')
	print()


for tc in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if l.index(max(l)) > l.index(min(l)):
		print(min(l), max(l))
	else:
		print(max(l), min(l))


def median(l):
	l.sort()
	return l[1]
t = int(input())
for i in range(t):
	n = int(input())
	numbers = list(map(int, input().split()))
	while len(numbers) >= 3:
		m = median(numbers[:3])
		numbers.remove(m)
	print(*numbers)


for _ in range(int(input())):
	length = int(input())
	num = list(map(int, input().split()))
	minv = min(num)
	maxv = max(num)
	minind = num.index(minv)
	maxind = num.index(maxv)
	if maxind > minind:
		print(minv, maxv)
	else:
		print(maxv, minv)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = a.copy()
	a.sort()
	x = min(a)
	y = max(a)
	if c.index(x) < c.index(y):
		print(x, y)
	else:
		print(y, x)


for _ in range(int(input())):
	n = int(input())
	seq = list(map(int, input().split()))
	a = min(seq)
	b = max(seq)
	for x in seq:
		if a == x:
			print(a, b)
			break
		elif b == x:
			print(b, a)
			break


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	while len(arr) > 2:
		sub = arr[:3]
		sub.sort()
		arr.remove(sub[1])
	print(arr[0], arr[1])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ma = max(a)
	mi = min(a)
	ima = a.index(ma)
	imi = a.index(mi)
	if ima > imi:
		print(str(mi) + ' ' + str(ma))
	else:
		print(str(ma) + ' ' + str(mi))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	mi = l.index(min(l))
	ma = l.index(max(l))
	if mi < ma:
		print(min(l), max(l))
	else:
		print(max(l), min(l))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = sorted(l)
	if l.index(l1[0]) < l.index(l1[-1]):
		print(l1[0], l1[-1])
	else:
		print(l1[-1], l1[0])


t = int(input())
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	minn = arr[0]
	max = 0
	min_i = 0
	max_i = 0
	for i in range(n):
		if arr[i] < minn:
			minn = arr[i]
			min_i = i
		if arr[i] > max:
			max = arr[i]
			max_i = i
	if max_i > min_i:
		print(str(minn) + ' ' + str(max))
	else:
		print(str(max) + ' ' + str(minn))


t = int(input())
while t > 0:
	n = int(input())
	x = list(map(int, input().split(' ', n - 1)))
	if x.index(min(x)) > x.index(max(x)):
		print(max(x), min(x))
	else:
		print(min(x), max(x))
	t = t - 1


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	(x, y) = (min(a), max(a))
	if a.index(x) > a.index(y):
		print(y, x)
	else:
		print(x, y)


t = int(input())
for it in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	while len(a) > 2:
		a.remove(sum(a[0:3]) - max(a[0:3]) - min(a[0:3]))
	print(a[0], a[1])


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	(a, b) = (min(A), max(A))
	if A.index(a) < A.index(b):
		print(a, b)
	else:
		print(b, a)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	(mn, mx) = (min(A), max(A))
	if A.index(mn) < A.index(mx):
		print(mn, mx)
	else:
		print(mx, mn)


t = int(input())
for v in range(t):
	n = int(input())
	l = list(map(int, input().split()))[:n]
	k = max(l)
	b = min(l)
	for c in range(len(l)):
		if l[c] == k:
			print(k, end=' ')
			print(b)
			break
		elif l[c] == b:
			print(b, end=' ')
			print(k)
			break


T = int(input())
for i in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	m1 = max(l)
	m2 = min(l)
	if l.index(m1) > l.index(m2):
		print(m2, m1)
	else:
		print(m1, m2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = min(a)
	c = max(a)
	for i in range(n):
		if a[i] == b:
			e = i
		elif a[i] == c:
			f = i
	if e < f:
		print(b, c, sep=' ')
	else:
		print(c, b, sep=' ')


for _ in range(int(input())):
	n = int(input())
	m = [int(i) for i in input().split()]
	if m.index(max(m)) > m.index(min(m)):
		print(min(m), max(m))
	else:
		print(max(m), min(m))


from math import *
t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	ma = max(arr)
	mi = min(arr)
	i = arr.index(ma)
	j = arr.index(mi)
	if i < j:
		print(ma, mi)
	else:
		print(mi, ma)


for _ in range(int(input())):
	n = int(input())
	x = [int(i) for i in input().split(' ', n - 1)]
	if x.index(min(x)) > x.index(max(x)):
		print(max(x), min(x))
	else:
		print(min(x), max(x))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	(x, y) = (b[0], b[-1])
	if a.index(x) > a.index(y):
		print(y, x)
	else:
		print(x, y)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m1 = min(a)
	m2 = max(a)
	for i in a:
		if i == m1:
			print(m1, m2, end=' ')
			break
		elif i == m2:
			print(m2, m1, end=' ')
			break
	print()


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = min(a)
	d = max(a)
	for i in range(n):
		if k == a[i]:
			print(k, d)
			break
		elif d == a[i]:
			print(d, k)
			break


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	mi = min(l)
	ma = max(l)
	l2 = []
	for j in l:
		if j == mi:
			l2.append(mi)
		if j == ma:
			l2.append(ma)
	for j in l2:
		print(j, end=' ')
	print()


from statistics import median
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	while len(A) != 2:
		med = median(A[:3])
		A.remove(med)
	print(*A)


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	(x, y) = (min(A), max(A))
	if A.index(x) > A.index(y):
		print(y, x)
	else:
		print(x, y)


for t in range(int(input())):
	n = int(input())
	seq = list(map(int, input().split()))
	x = max(seq)
	y = min(seq)
	if seq.index(x) < seq.index(y):
		print(x, y)
	else:
		print(y, x)


t = int(input())
while t != 0:
	n = int(input())
	l = list(map(int, input().split()))
	g = max(l)
	s = min(l)
	if l.index(g) < l.index(s):
		print(g, s)
	else:
		print(s, g)
	t -= 1


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	while len(a) > 2:
		b = a[0:3]
		b.sort()
		a.remove(b[1])
	for i in a:
		print(i, end=' ')
	print()


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	m1 = min(l)
	m2 = max(l)
	for i in range(n):
		if l[i] == m1 or l[i] == m2:
			print(l[i], end=' ')
		else:
			continue
	print(' ')


for tc in range(int(input())):
	n = int(input())
	x = [int(x) for x in input().split()]
	a = min(x)
	b = max(x)
	if x.index(a) < x.index(b):
		print(a, b)
	else:
		print(b, a)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	c = a.index(b[0])
	d = a.index(b[n - 1])
	if c < d:
		print(a[c], a[d])
	else:
		print(a[d], a[c])


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()[:n]))
	x = min(lst)
	y = max(lst)
	if lst.index(x) < lst.index(y):
		print(x, end=' ')
		print(y)
	else:
		print(y, end=' ')
		print(x)


def fun(a, l):
	ll = []
	if l.index(min(l)) < l.index(max(l)):
		print(min(l), max(l))
	else:
		print(max(l), min(l))
for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	fun(a, l)