You're given a sequence of N distinct integers. You need to find a subsequence of length K with the maximum possible median.

The median of a sequence is the value of the element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is selected. For example, if the sequence is [3, 4, 2, 1, 5], then the median is 3 since after sorting, it will look like [1, 2, 3, 4, 5] and 3 is the only middle element. The median of [4, 2, 1, 5] is 2 since after sorting, the value 2 is the left of the two middle elements 2 and 4.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, if the sequence is [2, 1, 4, 5, 7], then [1, 5, 7], [2, 1, 4], [5] are some valid subsequences but [4, 1, 2], [1, 6, 7] are not.

------ Input Format ------ 

- The first line will contain T, the number of test cases. The description of test cases follow.
- The first line of each test case consists of two space-separated integers N, the length of the sequence, and K, the length of the subsequence to be found.
- The second line of each test case consists of N distinct space-separated integers A_{i}, the elements of the sequence.

------ Output Format ------ 

- For each test case, output two lines.
- The first line should consist of the median of the subsequence with the maximum median.
- The second line should consist of K space-separated integers, representing a subsequence with that median. If there are multiple such subsequences, print any.

------ Constraints ------ 

$1 ≤ T ≤ 30$
$1 ≤ K ≤ N ≤ 2 \times 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases won't exceed $5 \times 10^{5}$

----- Sample Input 1 ------ 
1
5 3
1 4 3 6 5
----- Sample Output 1 ------ 
5
1 6 5

Difficulty: MEDIUM_HARD
Tags: Sorting

Combinatorics

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
import math
t = int(input())
res1 = []
res2 = []
for i in range(t):
	(n, k) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	x = k // 2
	l1 = sorted(l)
	med = l1[-x - 1]
	c = 0
	lc = 1
	hc = 1
	print(med)
	for m in l:
		if c == k:
			break
		if m < med and lc <= math.ceil(k / 2) - 1:
			print(m, end=' ')
			lc = lc + 1
			c = c + 1
		if m == med:
			print(m, end=' ')
		if m > med and hc < math.ceil((k + 1) / 2):
			print(m, end=' ')
			hc = hc + 1
			c = c + 1


import math
try:
	no_of_testcases = int(input())
	for i in range(no_of_testcases):
		(n, k) = map(int, input().split())
		l = list(map(int, input().split()))
		sl = sorted(l, reverse=True)
		nk = math.ceil((k + 1) / 2)
		(count, low_count, high_count) = (0, 1, 1)
		req_max = sl[nk - 1]
		print(req_max)
		for m in l:
			if count == k:
				break
			if m < req_max and low_count <= math.ceil(k / 2) - 1:
				print(m, end=' ')
				low_count = low_count + 1
				count = count + 1
			if m == req_max:
				print(m, end=' ')
				count = count + 1
			if m > req_max and high_count <= nk - 1:
				print(m, end=' ')
				high_count = high_count + 1
				count = count + 1
		print()
except:
	pass


t = int(input())
while t > 0:
	t -= 1
	(N, K) = (int(num) for num in input().split())
	a = [int(num) for num in input().split()]
	if N == 1:
		print(a[0])
		print(a[0])
		continue
	arr = a[:]
	arr.sort()
	median = None
	for i in range(N - 1, -1, -1):
		L = i - 0
		R = N - i - 1
		if K % 2 == 0:
			if L >= K // 2 - 1 and R + 1 >= K // 2 + 1:
				median = arr[i]
				break
		else:
			req = K // 2
			if L >= req and R >= req:
				median = arr[i]
				break
	res = []
	if K % 2 == 0:
		L = K // 2 - 1
		R = K // 2
	else:
		L = K // 2
		R = K // 2
	for i in range(N):
		if L > 0 and a[i] < median:
			L -= 1
			res.append(str(a[i]))
		if R > 0 and a[i] > median:
			R -= 1
			res.append(str(a[i]))
		if a[i] == median:
			res.append(str(a[i]))
	print(median)
	print(' '.join(res))


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	reverseSortedA = sorted(A, reverse=True)
	maxMedian = reverseSortedA[K // 2]
	if K % 2 == 0:
		left = K // 2 - 1
		right = K // 2
	else:
		left = right = K // 2
	subsequence = []
	for i in A:
		if i < maxMedian and left > 0:
			subsequence.append(i)
			left -= 1
		elif i == maxMedian:
			subsequence.append(i)
		elif i > maxMedian and right > 0:
			subsequence.append(i)
			right -= 1
	print(maxMedian)
	print(*subsequence, sep=' ')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()[:n]))
	arrSort = sorted(arr, reverse=True)
	if k % 2 == 0:
		a = k // 2
		countPrv = k // 2 - 1
		countNext = countPrv + 1
	else:
		a = k // 2
		countPrv = k // 2
		countNext = countPrv
	median = arrSort[a]
	print(median)
	for item in arr:
		if item > arrSort[a] and countNext > 0:
			print(item, end=' ')
			countNext -= 1
		elif item < arrSort[a] and countPrv > 0:
			print(item, end=' ')
			countPrv -= 1
		elif item == arrSort[a]:
			print(item, end=' ')
	print()


from sys import stdin

def get_med_subseq(vals, sublen):
	mx = (sublen - 1) // 2
	med = sorted(vals)[-sublen + mx]
	if sublen == len(vals):
		return (med, vals)
	sseq = []
	for v in vals:
		if v >= med:
			sseq.append(v)
		elif mx:
			sseq.append(v)
			mx -= 1
	return (med, sseq)
input = stdin.readline
T = int(input())
for tx in range(T):
	(N, K) = map(int, input().split())
	Ays = list(map(int, input().split()))
	(mdn, seq) = get_med_subseq(Ays, K)
	print(mdn, ' '.join(map(str, seq)), sep='\n')


for iii in range(int(input())):
	(n, k) = map(int, input().split())
	q = list(map(int, input().split()))
	w = [q[i] for i in range(n)]
	w.sort(reverse=True)
	ww = []
	for i in range(k):
		ww.append(w[i])
	ww = ww[::-1]
	x = (k + 1) // 2
	y = x - 1
	x = x - 1
	x = ww[x]
	count = 0
	print(x)
	for i in range(n):
		if q[i] >= x:
			print(q[i], end=' ')
		elif count < y:
			print(q[i], end=' ')
			count += 1
	print()


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	x = (k - 1) // 2
	a = s.copy()
	a.sort()
	m = a[n + x - k]
	st = ''
	print(m)
	t = 0
	for i in s:
		if i >= m:
			st += str(i) + ' '
		elif t < x:
			st += str(i) + ' '
			t += 1
	print(st)


for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	b = sorted(a)
	f = []
	if k % 2 == 0:
		le = k // 2 - 1
		se = k // 2
		m = k // 2 + 1
	else:
		le = se = k // 2
		m = k // 2 + 1
	me = b[-m]
	for i in a:
		if len(f) == k:
			break
		if i == me:
			f.append(str(i))
		elif i > me:
			if se != 0:
				se -= 1
				f.append(str(i))
		elif i < me:
			if le != 0:
				le -= 1
				f.append(str(i))
	print(me)
	print(' '.join(f))


for _ in range(int(input())):
	(n, k) = input().split()
	L = list(map(int, input().split()))
	X = sorted(L)
	r = len(L) - 1
	l = r - int(k) + 1
	mid = (l + r) // 2
	print(X[mid])
	arr = []
	if int(k) % 2 == 0:
		x = (int(k) - 1) // 2
		y = int(k) // 2
	elif int(k) % 2 != 0:
		x = (int(k) - 1) // 2
		y = (int(k) - 1) // 2
	for i in range(int(n)):
		if L[i] < X[mid] and x > 0:
			arr.append(L[i])
			x -= 1
		elif L[i] > X[mid] and y > 0:
			arr.append(L[i])
			y -= 1
		elif L[i] == X[mid]:
			arr.append(L[i])
	for k in arr:
		print(k, end=' ')


import sys

def input():
	return sys.stdin.readline().rstrip('\r\n')

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

def A():
	for _ in range(*maps()):
		a = [*maps()]
		b = [*maps()]
		if a.count(1) == b.count(1) and a.count(0) == b.count(0):
			print('Pass')
		else:
			print('Fail')

def B():
	from collections import defaultdict
	for _ in range(*maps()):
		(n, k, l) = maps()
		a = [*maps()]
		mx = 0
		d = defaultdict(int)
		for i in a:
			d[i] += 1
			mx = max(mx, i)
		if d[mx] == 1 and a[-1] == mx:
			print('Yes')
			continue
		if a[-1] != mx and k <= 0:
			print('No')
			continue
		f = a[-1] + k * (l - 1)
		if f > mx:
			print('Yes')
		else:
			print('No')
result = []

def backtrack(nums, start, curr_set):
	result.append(list(curr_set))
	for i in range(start, len(nums)):
		if i > start and nums[i] == nums[i - 1]:
			continue
		curr_set.append(nums[i])
		backtrack(nums, i + 1, curr_set)
		curr_set.pop()

def AllSubsets(nums):
	curr_set = []
	nums.sort()
	backtrack(nums, 0, curr_set)

def naive(n, k, a):
	mx = 0
	if k % 2:
		idx = k // 2
	else:
		idx = k // 2 - 1
	AllSubsets(a)
	for i in result:
		if len(i) == k:
			f = sorted(i)
			if f[idx] > mx:
				mx = f[idx]
				A = i
	result.clear()
	return (mx, A)

def C():
	for _ in range(*maps()):
		(n, k) = maps()
		a = [*maps()]
		if k == n:
			print(sorted(a)[k // 2 - (1 if k % 2 == 0 else 0)])
			print(*a)
			continue
		if k == 1:
			idx = a.index(max(a))
			print(a[idx], a[idx], sep='\n')
			continue
		d = {}
		for i in range(n):
			d[a[i]] = i
		if k % 2:
			idx = k // 2
			l = k // 2 - 1
			r = n - k // 2
		else:
			idx = k // 2 - 1
			l = idx
			r = n - idx - 1
		mx = 0
		d = {}
		A = sorted(a)
		for i in range(n):
			d[A[i]] = i
		for i in range(n):
			if a[i] > mx and d[a[i]] < r:
				mx = a[i]
				idx = i
		t = []
		F = k // 2 - (1 if k % 2 == 0 else 0)
		for i in range(n):
			if len(t) == F:
				break
			if a[i] < mx:
				t.append((a[i], i))
		t.append((a[idx], idx))
		for i in range(n):
			if len(t) == k:
				break
			if a[i] > mx:
				t.append((a[i], i))
		t.sort(key=lambda x: x[1])
		X = [i for (i, j) in t]
		Y = sorted(X)[k // 2 - (1 if k % 2 == 0 else 0)]
		print(Y)
		print(*X)
C()


te = int(input())
for t in range(te):
	test = input().split(' ')
	N = int(test[0])
	K = int(test[1])
	arr = list(map(int, input().split(' ')))
	arrSorted = arr.copy()
	arrSorted.sort()
	if K == 0:
		print(max(arr))
	median = arrSorted[N - K // 2 - 1]
	c = 0
	print(median)
	res = ''
	for n in arr:
		if n < median and c < (K + 1) // 2 - 1:
			c += 1
			res += str(n) + ' '
		elif n >= median:
			res += str(n) + ' '
	print(res)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = []
	array_of_ints = [int(num) for num in input().split()]
	arr += array_of_ints
	x = k // 2 + 1
	arr1 = sorted(arr)
	arr1.reverse()
	y = k - x
	z = k - y - 1
	res = []
	tar = arr1[x - 1]
	for i in arr:
		if y > 0 and i < tar:
			res.append(i)
			y -= 1
		if z > 0 and i > tar:
			res.append(i)
			z -= 1
		if tar == i:
			res.append(i)
	print(tar)
	for i in res:
		print(i, end=' ')


def solve():
	(n, k) = list(map(int, input().split()))
	p = k
	l1 = list(map(int, input().split()))
	l2 = l1.copy()
	l2.sort()
	eve = False
	if k % 2 == 0:
		k += 1
		eve = True
	num = k // 2
	check = True
	first = True
	while check:
		mid = l2[-1 * (num + 1)]
		print(mid)
		l = 0
		l_t = num
		r_t = k - num - 1
		if eve:
			l_t -= 1
		res = []
		for ele in l1:
			if l_t > 0 and ele < mid:
				res.append(ele)
				l += 1
				l_t -= 1
			elif r_t > 0 and ele > mid:
				res.append(ele)
				l += 1
				r_t -= 1
			elif ele == mid:
				res.append(ele)
				l += 1
			if l == p:
				print(*res)
				return
		num += 1
for _ in range(int(input())):
	solve()


import sys
testcases = int(input())
while testcases > 0:
	(n, k) = map(int, sys.stdin.readline().split())
	el = list(map(int, sys.stdin.readline().split()))
	el2 = sorted(el)
	median = 0
	el2 = el2[n - k:n]
	if k % 2 == 0:
		median = el2[k // 2 - 1]
		l = k // 2 - 1
		r = k // 2
	else:
		median = el2[k // 2]
		l = k // 2
		r = k // 2
	print(median)
	for i in el:
		if i < median and l > 0:
			print(i, end=' ')
			l -= 1
		elif i == median:
			print(i, end=' ')
		elif i > median and r > 0:
			print(i, end=' ')
			r -= 1
	print()
	testcases -= 1


for t in range(int(input())):
	(N, K) = input().split()
	(n, k) = (int(N), int(K))
	arr = [int(x) for x in input().split()]
	a = sorted(arr)
	ans = [0] * k
	if k % 2 == 0:
		f = k // 2 - 1
		b = k // 2 + 1
	else:
		f = k // 2
		b = k // 2 + 1
	for i in range(f):
		ans[i] = a[i]
	for j in range(b):
		ans[k - j - 1] = a[n - j - 1]
	if k % 2 == 0:
		m = ans[k // 2 - 1]
	else:
		m = ans[k // 2]
	i = 0
	cf = 0
	cb = 0
	l = []
	while i < n and cf < f and (cb < b):
		if arr[i] < m:
			cf += 1
			l.append(arr[i])
		else:
			l.append(arr[i])
			cb += 1
		i += 1
	if cf == f:
		while i < n and cb < b:
			if arr[i] >= m:
				cb += 1
				l.append(arr[i])
			i += 1
	else:
		while i < n and cf < f:
			if arr[i] < m:
				cf += 1
				l.append(arr[i])
			i += 1
	print(m)
	print(*l)


def get_subseq(a, n, k):
	b = [i for i in range(n)]
	b.sort(key=lambda x: -a[x])
	ind = b[k // 2]
	before = (k - 1) // 2
	after = k // 2
	ans = []
	c = 0
	d = 0
	for i in range(len(a)):
		if i == ind:
			ans.append(a[i])
		elif c < before and a[i] < a[ind]:
			ans.append(a[i])
			c += 1
		elif d < after and a[i] > a[ind]:
			ans.append(a[i])
			d += 1
	print(a[ind])
	print(' '.join(map(str, ans)))
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	get_subseq(a, n, k)


import heapq
import math
for i in range(0, int(input())):
	(uuu, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = []
	counter = 0
	n = [0]
	for j in range(0, uuu):
		s.append(0)
	heapq.heapify(n)
	b = math.ceil(k / 2)
	l = sorted(arr)
	counter = 0
	t = 0
	for i in range(uuu - 1, -1, -1):
		counter = counter + 1
		if counter == b:
			if k % 2 == 0:
				t = l[i - 1]
			else:
				t = l[i]
	if k % 2 == 0:
		req = k / 2 - 1
	else:
		req = k // 2
	p = []
	for i in range(0, uuu):
		if req > 0 and arr[i] < t:
			p.append(arr[i])
			req = req - 1
		elif arr[i] >= t:
			p.append(arr[i])
	print(t)
	for i in range(0, len(p)):
		print(p[i], end=' ')
	print()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ss = sorted(l)
	t = n - k
	x = ss[t:]
	med = 0
	if k % 2 == 0:
		med = x[int(k / 2) - 1]
	else:
		med = x[k // 2]
	print(med)
	bef = 0
	af = 0
	if k % 2 != 0:
		bef = k // 2
		af = k // 2
	else:
		bef = int(k / 2) - 1
		af = int(k / 2)
	see = 0
	for i in range(n):
		if bef == 0 and af == 0:
			break
		elif l[i] < med and bef > 0:
			print(l[i], end=' ')
			bef -= 1
			continue
		elif l[i] > med and af > 0:
			print(l[i], end=' ')
			af -= 1
			continue
		elif l[i] == med:
			print(med, end=' ')
			see = 1
	if see == 0:
		print(med, end=' ')
	print()


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	m = sorted(l, reverse=True)
	ans = m[b // 2]
	if b & 1:
		(x, y) = (b // 2, (b + 1) // 2)
	else:
		(x, y) = (b // 2 - 1, b // 2 + 1)
	sol = []
	c = 0
	for i in l:
		if x == 0 and y == 0 and (c == 1):
			break
		if i < ans and x != 0:
			sol += [i]
			x -= 1
		if i > ans and y != 0:
			sol += [i]
			y -= 1
		if i == ans:
			sol += [i]
			c += 1
	print(ans)
	print(*sol)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	x = sorted(a)[n - k:][k - 1 >> 1]
	print(x)
	y = k - 1 >> 1
	z = k - y - 1
	for b in a:
		if b < x and y > 0:
			print(b, end=' ')
			y -= 1
		elif b > x and z > 0:
			print(b, end=' ')
			z -= 1
		elif b == x:
			print(b, end=' ')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = []
	c = []
	x = y = 0
	for j in a:
		b.append(j)
	a.sort()
	for j in range(n - k, n):
		c.append(a[j])
	med = c[(k + 1) // 2 - 1]
	print(med)
	for j in b:
		if x < (k + 1) // 2 - 1 and j < med:
			print(j, end=' ')
			x = x + 1
		if y < k - (k + 1) // 2 and j > med:
			print(j, end=' ')
			y = y + 1
		if j == med:
			print(j, end=' ')
	print()


import math, os, io, heapq
from sys import stdin, stdout
from collections import Counter, deque, defaultdict
from itertools import product
import bisect

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def solve():
	(n, k) = getList()
	a = getList()
	idmap = {v: i for (i, v) in enumerate(a)}
	b = sorted(a)
	(med, bef) = (b[n - k // 2 - 1], k // 2 if k % 2 else k // 2 - 1)
	vals = []
	for i in range(bef):
		vals.append(idmap[b[i]])
	for i in range(n - k // 2 - 1, n):
		vals.append(idmap[b[i]])
	vals.sort()
	for i in range(len(vals)):
		vals[i] = a[vals[i]]
	print(med)
	print(*vals)
for _ in range(getInt()):
	solve()


t = int(input())
while t > 0:
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	B = []
	for i in range(N):
		B.append(A[i])
	B.sort()
	C = B[N - K:]
	if K % 2 == 0:
		median = C[K // 2 - 1]
	else:
		median = C[K // 2]
	m = A.index(median)
	countsmall = 0
	countlarge = 0
	ans = []
	if K % 2 == 0:
		for j in range(N):
			if j < m:
				if A[j] < median:
					if countsmall < K // 2 - 1:
						ans.append(A[j])
						countsmall += 1
				if A[j] > median:
					if countlarge < K // 2:
						ans.append(A[j])
						countlarge += 1
			elif j == m:
				ans.append(median)
			elif j > m:
				if A[j] < median:
					if countsmall < K // 2 - 1:
						ans.append(A[j])
						countsmall += 1
				if A[j] > median:
					if countlarge < K // 2:
						ans.append(A[j])
						countlarge += 1
	if K % 2 != 0:
		for j in range(N):
			if j < m:
				if A[j] < median:
					if countsmall < K // 2:
						ans.append(A[j])
						countsmall += 1
				if A[j] > median:
					if countlarge < K // 2:
						ans.append(A[j])
						countlarge += 1
			elif j == m:
				ans.append(median)
			elif j > m:
				if A[j] < median:
					if countsmall < K // 2:
						ans.append(A[j])
						countsmall += 1
				if A[j] > median:
					if countlarge < K // 2:
						ans.append(A[j])
						countlarge += 1
	print(median)
	print(*ans, end=' ')
	print()
	t = t - 1


import sys
from statistics import median
input = sys.stdin.readline
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = [*map(int, input().split())]
	b = sorted(a)
	m = 0
	b = b[n - k:n]
	if k % 2 == 0:
		m = b[k // 2 - 1]
		print(m)
		x = k // 2 - 1
		y = k // 2
		for i in a:
			if i < m and x > 0:
				print(i, end=' ')
				x -= 1
			elif i == m:
				print(i, end=' ')
			elif i > m and y > 0:
				print(i, end=' ')
				y -= 1
		print()
	else:
		m = b[k // 2]
		print(m)
		x = k // 2
		y = k // 2
		for i in a:
			if i < m and x > 0:
				print(i, end=' ')
				x -= 1
			elif i == m:
				print(i, end=' ')
			elif i > m and y > 0:
				print(i, end=' ')
				y -= 1
		print()
	t -= 1