Given an array of integers arr and an integer k.
A value arr[i] is said to be stronger than a value arr[j] if |arr[i] - m| > |arr[j] - m| where m is the median of the array.
If |arr[i] - m| == |arr[j] - m|, then arr[i] is said to be stronger than arr[j] if arr[i] > arr[j].
Return a list of the strongest k values in the array. return the answer in any arbitrary order.
Median is the middle value in an ordered integer list. More formally, if the length of the list is n, the median is the element in position ((n - 1) / 2) in the sorted list (0-indexed).

For arr = [6, -3, 7, 2, 11], n = 5 and the median is obtained by sorting the array arr = [-3, 2, 6, 7, 11] and the median is arr[m] where m = ((5 - 1) / 2) = 2. The median is 6.
For arr = [-7, 22, 17, 3], n = 4 and the median is obtained by sorting the array arr = [-7, 3, 17, 22] and the median is arr[m] where m = ((4 - 1) / 2) = 1. The median is 3.

 
Example 1:
Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,1,4,2,3]. The strongest 2 elements are [5, 1]. [1, 5] is also accepted answer.
Please note that although |5 - 3| == |1 - 3| but 5 is stronger than 1 because 5 > 1.

Example 2:
Input: arr = [1,1,3,5,5], k = 2
Output: [5,5]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,5,1,1,3]. The strongest 2 elements are [5, 5].

Example 3:
Input: arr = [6,7,11,7,6,8], k = 5
Output: [11,8,6,6,7]
Explanation: Median is 7, the elements of the array sorted by the strongest are [11,8,6,6,7,7].
Any permutation of [11,8,6,6,7] is accepted.

Example 4:
Input: arr = [6,-3,7,2,11], k = 3
Output: [-3,11,2]

Example 5:
Input: arr = [-7,22,17,3], k = 2
Output: [22,17]

 
Constraints:

1 <= arr.length <= 10^5
-10^5 <= arr[i] <= 10^5
1 <= k <= arr.length

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Sorting

Amortized analysis

Starter code: class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        

Solutions:
class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		(i, j) = (0, len(arr) - 1)
		median = arr[(len(arr) - 1) // 2]
		while len(arr) + i - j <= k:
			if median - arr[i] > arr[j] - median:
				i = i + 1
			else:
				j = j - 1
		return arr[:i] + arr[j + 1:]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		ans = []
		lt = 0
		pt = len(arr) - 1
		m = arr[(len(arr) - 1) // 2]
		for i in range(k):
			left = abs(arr[lt] - m)
			right = abs(arr[pt] - m)
			if right >= left:
				ans.append(arr[pt])
				pt -= 1
			else:
				ans.append(arr[lt])
				lt += 1
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		n = len(arr)
		m = arr[(n - 1) // 2]
		res = []
		(i, j) = (0, n - 1)
		while k > 0:
			if arr[j] - m >= m - arr[i]:
				res.append(arr[j])
				j -= 1
			else:
				res.append(arr[i])
				i += 1
			k -= 1
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		heap = []
		for num in arr:
			if len(heap) >= n // 2 + 1:
				heapq.heappushpop(heap, num)
			else:
				heapq.heappush(heap, num)
		median = heap[0]
		heap = []
		for num in arr:
			if len(heap) >= k:
				heapq.heappushpop(heap, (abs(median - num), num))
			else:
				heapq.heappush(heap, (abs(median - num), num))
		return [num for (_, num) in heap]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		if not arr or n == 0:
			return []
		arr.sort()
		m = arr[(n - 1) // 2]
		return sorted(arr, reverse=True, key=lambda x: (abs(x - m), x))[:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		median = sorted(arr)[(len(arr) - 1) // 2]
		return sorted(arr, key=lambda x: (-abs(x - median), -x))[:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		nums = sorted(arr)
		median = nums[(len(nums) - 1) // 2]
		arr.sort(key=lambda x: (abs(x - median), x), reverse=True)
		res = []
		for num in arr:
			res.append(num)
			k -= 1
			if k == 0:
				break
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		N = len(arr)
		arr.sort()
		median = arr[(N - 1) // 2]
		heap = []
		for n in arr:
			heapq.heappush(heap, (-abs(n - median), -n, n))
		ans = []
		for _ in range(k):
			ans.append(heapq.heappop(heap)[-1])
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		import heapq
		heap = []
		arr = sorted(arr)
		median = arr[(len(arr) - 1) // 2]
		for (i, num) in enumerate(arr):
			heapq.heappush(heap, (abs(num - median), num))
			if len(heap) > k:
				heapq.heappop(heap)
		return [item[1] for item in heap]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		median = arr[int((len(arr) - 1) / 2)]
		strong = {}
		for x in arr:
			val = abs(x - median)
			if val not in list(strong.keys()):
				strong[abs(x - median)] = [x]
			else:
				strong[abs(x - median)].append(x)
		strong = sorted(list(strong.items()), reverse=True)
		strongest = []
		for x in strong:
			for val in sorted(x[1], reverse=True):
				if len(strongest) == k:
					break
				strongest.append(val)
		return strongest


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		mid = (len(arr) - 1) // 2
		m = arr[mid]
		temp = sorted(arr, key=lambda x: abs(x - m))
		return temp[-1 * k:]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		if k >= len(arr):
			return arr
		median = self.get_median(arr)
		results = [(math.fabs(arr[x] - median), arr[x]) for x in range(len(arr))]
		results.sort()
		return [results[-i - 1][1] for i in range(k)]

	def get_median(self, arr):
		arr_sorted = sorted(arr)
		idx = int((len(arr) - 1) / 2)
		return arr_sorted[idx]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		if k == n:
			return arr
		arr.sort()
		med = arr[(len(arr) - 1) // 2]
		sorted_diff = sorted(arr, key=lambda x: abs(x - med))
		return sorted_diff[-k:]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		res = []
		val = arr[(len(arr) - 1) // 2]
		arr.sort(key=lambda x: (abs(x - val), x), reverse=True)
		return arr[:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		med = sorted(arr)[(len(arr) - 1) // 2]
		return sorted(arr, key=lambda x: (abs(x - med), x), reverse=True)[:k]


class Solution:

	def getStrongest(self, lis: List[int], k: int) -> List[int]:
		n = len(lis)
		lis.sort()
		med = lis[(n - 1) // 2]
		ans = [[abs(med - lis[i]), lis[i]] for i in range(n)]
		ans.sort(reverse=True)
		fin = []
		for i in range(k):
			fin.append(ans[i][1])
		return fin


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		res = []
		valuearr = []
		arr.sort()
		m = arr[int((len(arr) - 1) / 2)]
		for i in arr:
			value = []
			value.append(i)
			value.append(abs(i - m))
			valuearr.append(value)
		valuearr.sort(key=lambda x: (x[1], x[0]), reverse=True)
		for i in range(k):
			res.append(valuearr[i][0])
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		arr_pair = [(i, arr[i]) for i in range(n)]
		arr_pair.sort(key=lambda x: x[1])
		median = arr_pair[(n - 1) // 2][1]
		max_val = max([abs(x) for x in arr])
		arr_pair = [(x[0], abs(x[1] - median)) for x in arr_pair]
		arr_pair.sort(key=lambda x: (x[1], arr[x[0]]))
		return [arr[x[0]] for x in arr_pair[-k:]]


class Solution:

	def get_median(self, arr):
		arr.sort()
		n = len(arr)
		return arr[(n - 1) // 2]

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		StrengthIndexAndVal = collections.namedtuple('StrengthIndexAndVal', ('strength', 'index', 'val'))
		if len(arr) == 0:
			return []
		m = self.get_median(arr)
		heap = []
		for (i, val) in enumerate(arr):
			siv = StrengthIndexAndVal(abs(val - m), i, val)
			if len(heap) == k:
				heapq.heappushpop(heap, siv)
			else:
				heapq.heappush(heap, siv)
		return [x.val for x in heap]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		d = {}
		sort = sorted(arr)
		if n % 2 == 1:
			m = sort[n // 2]
		else:
			m = sort[(n - 1) // 2]
		for num in arr:
			val = abs(num - m)
			if val not in d:
				d[val] = []
			d[val].append(num)
		items = sorted(list(d.items()), reverse=True)
		i = 0
		ret = []
		while i < len(items) and k > 0:
			if k >= len(items[i][1]):
				ret.extend(items[i][1])
				k -= len(items[i][1])
			else:
				break
			i += 1
		if k > 0:
			items[i][1].sort()
			for j in range(k):
				ret.append(items[i][1][len(items[i][1]) - j - 1])
		return ret


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		arr_len = len(arr)
		m = arr[(arr_len - 1) // 2]
		(i, j) = (0, arr_len - 1)
		toret = []
		size = 0
		while i <= j and size < k:
			if abs(arr[i] - m) > abs(arr[j] - m):
				toret.append(arr[i])
				i += 1
			else:
				toret.append(arr[j])
				j -= 1
			size += 1
		return toret


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		lastPointer = -1
		startPointer = 0
		mInd = (len(arr) - 1) // 2
		m = arr[mInd]
		res = []
		for i in range(k):
			if abs(arr[lastPointer] - m) >= abs(arr[startPointer] - m):
				res.append(arr[lastPointer])
				lastPointer -= 1
			else:
				res.append(arr[startPointer])
				startPointer += 1
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		arr = sorted(arr)
		m = -1
		if n % 2 == 0:
			m = arr[(n - 1) // 2]
		else:
			m = arr[n // 2]
		ans = []
		left = 0
		right = n - 1
		while k > 0:
			if abs(arr[left] - m) > abs(arr[right] - m):
				ans.append(arr[left])
				left += 1
			else:
				ans.append(arr[right])
				right -= 1
			k -= 1
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		median = sorted(arr)[(len(arr) - 1) // 2]
		median_sorted_array = sorted(((i, val) for (i, val) in enumerate(arr)), key=lambda x: (abs(x[1] - median), x[1]), reverse=True)
		return [x[1] for x in median_sorted_array[:k]]


import random

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		median = sorted(arr)[(len(arr) - 1) // 2]
		return sorted(arr, key=lambda x: [abs(x - median), x], reverse=True)[:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		import heapq
		n = len(arr)
		sort = sorted(arr)
		if n % 2 == 1:
			m = sort[n // 2]
		else:
			m = sort[(n - 1) // 2]
		heap = []
		heapq.heapify(heap)
		for num in arr:
			val = abs(num - m)
			heapq.heappush(heap, (-val, -num))
		ret = []
		for i in range(k):
			(val, num) = heapq.heappop(heap)
			ret.append(-num)
		return ret


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		res = []
		arr.sort()
		j = len(arr) - 1
		if j == 0:
			return arr
		median = arr[j // 2]
		i = 0
		count = 1
		while count <= k:
			if abs(arr[i] - median) > abs(arr[j] - median):
				res.append(arr[i])
				i += 1
			elif abs(arr[i] - median) == abs(arr[j] - median):
				res.append(arr[j])
				j -= 1
			else:
				res.append(arr[j])
				j -= 1
			count += 1
		return res


import heapq

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		m = arr[(len(arr) - 1) // 2]
		for i in range(len(arr)):
			arr[i] = (abs(m - arr[i]), arr[i])
		arr.sort(reverse=True)
		return [arr[i][1] for i in range(k)]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		N = len(arr)
		median = arr[(N - 1) // 2]
		lp = 0
		rp = N - 1
		output = []
		for i in range(k):
			lps = abs(arr[lp] - median)
			rps = abs(arr[rp] - median)
			if rps >= lps:
				output.append(arr[rp])
				rp -= 1
				continue
			else:
				output.append(arr[lp])
				lp += 1
		return output


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		h = (len(arr) - 1) // 2
		median = arr[h]
		count = 0
		result = []
		i = 0
		j = len(arr) - 1
		while count < k and i <= j:
			strengthI = abs(arr[i] - median)
			strengthJ = abs(arr[j] - median)
			if strengthI == strengthJ:
				if arr[i] > arr[j]:
					result.append(arr[i])
					i += 1
				else:
					result.append(arr[j])
					j -= 1
			elif strengthI > strengthJ:
				result.append(arr[i])
				i += 1
			else:
				result.append(arr[j])
				j -= 1
			count += 1
		return result


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		n = len(arr)
		median = arr[(n - 1) // 2]
		i = 0
		j = n - 1
		ans = []
		for _ in range(k):
			s1 = abs(arr[i] - median)
			s2 = abs(arr[j] - median)
			if s1 > s2:
				ans.append(arr[i])
				i += 1
			elif s1 == s2:
				if arr[i] > arr[j]:
					ans.append(arr[i])
					i += 1
				else:
					ans.append(arr[j])
				j -= 1
			else:
				ans.append(arr[j])
				j -= 1
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		(start, end) = (0, len(arr) - 1)
		res = []
		l = len(arr)
		med = arr[end // 2]
		is_greater = lambda x, y: abs(x - med) > abs(y - med)
		while end >= start:
			if is_greater(arr[start], arr[end]):
				res.append(arr[start])
				start += 1
			else:
				res.append(arr[end])
				end -= 1
		return res[:k]


from typing import List

class Solution:

	def strengths(self, arr, length):
		ans = []
		m = arr[(length - 1) // 2]
		for i in arr:
			ans.append(abs(m - i))
		return ans

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		length = len(arr)
		ans = []
		arr.sort()
		strength = self.strengths(arr, length)
		count = 0
		i = 0
		a = length - 1
		while count < k and i != a:
			if strength[a] > strength[i]:
				ans.append(arr[a])
				a -= 1
			elif strength[a] < strength[i]:
				ans.append(arr[i])
				i += 1
			elif arr[a] > arr[i]:
				ans.append(arr[a])
				a -= 1
			else:
				ans.append(arr[i])
				i += 1
			count += 1
		if count < k and i == a:
			ans.append(arr[(length - 1) // 2])
		return ans


from collections import defaultdict

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr = sorted(arr)
		n = len(arr)
		median = arr[(n - 1) // 2]
		(l, r) = (0, n - 1)
		res = []
		for i in range(k):
			if abs(arr[l] - median) > abs(arr[r] - median):
				res.append(arr[l])
				l += 1
			else:
				res.append(arr[r])
				r -= 1
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		if len(arr) == 0:
			return []
		if k == len(arr):
			return sorted(arr)
		arr.sort()
		l = len(arr)
		med = arr[(l - 1) // 2]
		arr = [(abs(n - med), n) for n in arr]
		from functools import cmp_to_key

		def cmp(x, y):
			if x[0] == y[0]:
				if x[1] > y[1]:
					return -1
				elif x[1] < y[1]:
					return 1
				else:
					return 0
			elif x[0] > y[0]:
				return -1
			else:
				return 1
		res = sorted(arr, key=cmp_to_key(cmp))
		return [res[i][1] for i in range(k)]


from collections import defaultdict

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		new_a = sorted(arr)
		median = new_a[(n - 1) // 2]
		d = defaultdict(list)
		for x in arr:
			d[abs(x - median)].append(x)
		d = sorted(d.items(), key=lambda x: x[0], reverse=1)
		res = []
		for x in d:
			if len(x[1]) <= k:
				res += x[1]
				k -= len(x[1])
			else:
				tar = sorted(x[1])[::-1]
				i = 0
				while k > 0:
					res.append(tar[i])
					k -= 1
					i += 1
				return res
		return res


import heapq

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr = sorted(arr)
		length = len(arr)
		median = arr[(len(arr) - 1) // 2]
		print()
		print(median)
		heap = []
		cnt = k
		for i in range(length):
			heapq.heappush(heap, (abs(arr[i] - median), arr[i]))
			cnt -= 1
			if cnt < 0:
				heapq.heappop(heap)
		res = []
		while heap:
			res.append(heapq.heappop(heap)[1])
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		sorted_arr = sorted(arr)
		m = sorted_arr[(len(arr) - 1) // 2]
		num_dist = [(e, abs(e - m)) for e in sorted_arr]
		num_dist.sort(key=lambda x: x[0], reverse=True)
		num_dist.sort(key=lambda x: x[1], reverse=True)
		ans = [e[0] for e in num_dist]
		return ans[:k]


class Solution:

	def getStrongest(self, arr: List[int], K: int) -> List[int]:
		arr.sort()
		length = len(arr)
		res = arr[(length - 1) // 2]
		i = 0
		j = length - 1
		result = []
		while K > 0:
			a = abs(arr[i] - res)
			b = abs(arr[j] - res)
			if a > b or (a == b and arr[i] > arr[j]):
				result.append(arr[i])
				i += 1
			else:
				result.append(arr[j])
				j -= 1
			K -= 1
		return result


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr_new = sorted(arr)
		med = arr_new[int((len(arr) - 1) / 2)]
		i = 0
		j = 1
		output = []
		while True:
			if len(output) >= k:
				break
			elif abs(arr_new[-j] - med) >= abs(arr_new[i] - med):
				output.append(arr_new[-j])
				j += 1
			else:
				output.append(arr_new[i])
				i += 1
		return output


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		median: int = arr[(len(arr) - 1) // 2]
		ans: List[int] = []
		left: int = 0
		right: int = len(arr) - 1
		while len(ans) < k:
			if abs(arr[left] - median) > abs(arr[right] - median):
				ans.append(arr[left])
				left += 1
			else:
				ans.append(arr[right])
				right -= 1
		return ans


from queue import PriorityQueue

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		if not arr or len(arr) < 1:
			return []
		if len(arr) == 1:
			return arr
		arr.sort()
		heap = []
		median = arr[(len(arr) - 1) // 2]
		for x in arr:
			heapq.heappush(heap, (abs(x - median), x))
			if len(heap) > k:
				heapq.heappop(heap)
		return [heapq.heappop(heap)[1] for _ in range(k)]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		arr.sort(reverse=True)
		m = arr[ceil((n - 1) / 2)]
		arr.sort(key=lambda x: abs(x - m), reverse=True)
		return arr[:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		median = arr[(len(arr) - 1) // 2]
		arr.sort(key=lambda x: (abs(x - median), x), reverse=True)
		print((arr, median))
		return arr[:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		import functools

		def comparator(n1, n2):
			if abs(n1 - m) > abs(n2 - m):
				return 1
			if abs(n1 - m) < abs(n2 - m):
				return -1
			if abs(n1 - m) == abs(n2 - m):
				if n1 > n2:
					return 1
				elif n1 < n2:
					return -1
				else:
					return 0
			return 0
		arr.sort()
		n = len(arr)
		m = arr[(n - 1) // 2]
		new = sorted(arr, key=functools.cmp_to_key(comparator), reverse=True)
		return new[:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		arr = sorted(arr)
		m = -1
		if n % 2 == 0:
			m = arr[(n - 1) // 2]
		else:
			m = arr[n // 2]
		arr = sorted(arr, key=lambda x: (abs(x - m), x))
		return arr[-k:]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		s = sorted(arr)
		i = (len(arr) - 1) // 2
		m = s[i]
		strengths = []
		for item in s:
			st = abs(item - m)
			strengths.append((st, item))
		sorted_strengths = sorted(strengths, reverse=True)
		sorted_vals = []
		for ss in sorted_strengths:
			sorted_vals.append(ss[1])
		return sorted_vals[:k]


import heapq

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		index = len(arr) // 2 - (1 - len(arr) % 2)
		median = sorted(arr)[index]
		heap = []
		for (i, el) in enumerate(arr):
			heapq.heappush(heap, (-abs(el - median), -el))
		els = heapq.nsmallest(k, heap, key=lambda x: (x[0], x[1]))
		return [-el[1] for el in els]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		out = []
		arr.sort()
		l = 0
		h = len(arr) - 1
		m = arr[int(h / 2)]
		while l <= h:
			if abs(arr[l] - m) > abs(arr[h] - m):
				out.append(arr[l])
				l += 1
			else:
				out.append(arr[h])
				h -= 1
		return out[0:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		cnt = len(arr)
		arr = sorted(arr)
		mid_id = (cnt - 1) // 2
		mid = arr[mid_id]
		if k == cnt:
			return arr
		curr = 0
		res = []
		(left, right) = (0, cnt - 1)
		while curr < k:
			if abs(arr[right] - mid) >= abs(mid - arr[left]):
				res.append(arr[right])
				right -= 1
			else:
				res.append(arr[left])
				left += 1
			curr += 1
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr = sorted(arr)
		l = len(arr)
		if l % 2 == 0:
			median = arr[(l - 1) // 2]
		else:
			median = arr[l // 2]
		print(median)
		s = sorted(arr, key=lambda x: (-abs(x - median), -x))
		print(s)
		return s[:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		n = len(arr)
		m = arr[(n - 1) // 2]
		ans = []
		(lo, hi) = (0, n - 1)
		while lo <= hi and k > 0:
			(dlo, dhi) = (abs(arr[lo] - m), abs(arr[hi] - m))
			if dlo > dhi:
				ans.append(arr[lo])
				lo += 1
			else:
				ans.append(arr[hi])
				hi -= 1
			k -= 1
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		n = len(arr)
		median = arr[(n - 1) // 2]
		(left, right) = (0, n - 1)
		result = []
		while k > 0 and left <= right:
			if arr[right] - median >= median - arr[left]:
				result.append(arr[right])
				right = right - 1
			else:
				result.append(arr[left])
				left = left + 1
			k = k - 1
		return result


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr = sorted(arr)
		n = len(arr)
		if k == n:
			return arr
		if n % 2 == 0:
			median = arr[n // 2 - 1]
		else:
			median = arr[n // 2]
		i = 0
		j = n - 1
		answer = []
		while True:
			if arr[j] - median >= median - arr[i]:
				answer.append(arr[j])
				j -= 1
			else:
				answer.append(arr[i])
				i += 1
			if len(answer) == k:
				return answer


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		sarr = sorted(arr)
		L = len(arr)
		if L / 2 % 1 == 0:
			median = sarr[int((L - 1) / 2)]
		else:
			median = sarr[int(L / 2 - 0.5)]
		absm = [abs(a - median) for a in arr]
		tarr = [[absm[i], arr[i]] for i in range(L)]
		tarr = sorted(tarr, reverse=True)
		res = [tarr[i][1] for i in range(L) if i < k]
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		x = sorted(arr)
		l = len(arr)
		median = x[(l - 1) // 2]
		jj = sorted(list(range(len(arr))), key=lambda y: (abs(arr[y] - median), arr[y]), reverse=True)
		n = [arr[i] for i in jj]
		return n[:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		p = (len(arr) - 1) // 2
		med = arr[p]
		print(med)
		a1 = arr[:p]
		a2 = arr[p:]
		ans = []
		while k > 0:
			if len(a2) > 0 and len(a1) > 0:
				diff = abs(a2[-1] - med) - abs(a1[0] - med)
				if diff >= 0:
					ans.append(a2.pop(-1))
				else:
					ans.append(a1.pop(0))
			elif len(a2) > 0:
				ans.append(a2.pop(-1))
			elif len(a1) > 0:
				ans.append(a1.pop(0))
			k -= 1
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		med = arr[int((len(arr) - 1) / 2)]
		print(med)
		f = []
		while len(f) < k:
			rv = abs(arr[-1] - med)
			lv = abs(arr[0] - med)
			if rv >= lv:
				f.append(arr.pop(-1))
			else:
				f.append(arr.pop(0))
		return f


import heapq

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		if n == 0:
			return []
		arr.sort()
		median = arr[(n - 1) // 2]
		heap = []
		for num in arr:
			strength = abs(num - median)
			heapq.heappush(heap, (strength, num))
			if len(heap) > k:
				heapq.heappop(heap)
		ans = [heap[i][1] for i in range(min(k, n))]
		return ans
	pass


from typing import List

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		sorted_arrs = sorted(arr)
		n = len(arr)
		median = sorted_arrs[(n - 1) // 2]
		vals = [(abs(val - median), val) for val in arr]
		vals.sort()
		return [val for (comp, val) in vals[-k:]]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		m = arr[floor((len(arr) - 1) / 2)]
		res = []
		while len(res) < k:
			if abs(arr[-1] - m) >= abs(arr[0] - m):
				res.append(arr[-1])
				del arr[-1]
			else:
				res.append(arr[0])
				del arr[0]
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		svals = collections.defaultdict(list)
		median = sorted(arr)[(len(arr) - 1) // 2]
		for i in range(len(arr)):
			svals[abs(arr[i] - median)].append(arr[i])
		svals = sorted(svals.items(), key=lambda x: -x[0])
		res = []
		count = 0
		for tuplee in svals:
			flag = True
			for i in sorted(tuplee[1], reverse=True):
				res.append(i)
				count += 1
				if count == k:
					flag = False
					break
			if not flag:
				break
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		n = len(arr)
		mid = arr[(n - 1) // 2]
		h = collections.defaultdict(list)
		for i in arr:
			h[abs(i - mid)].append(i)
		sorted_data = sorted(h.items(), reverse=True)
		res = []
		for j in sorted_data:
			while len(j[1]) != 0:
				res.append(j[1].pop(-1))
				k -= 1
				if k == 0:
					return res
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		if len(arr) == 1:
			return arr
		arr.sort()
		med_loc = (len(arr) - 1) // 2
		median = arr[med_loc]
		count = 0
		ans = []
		while count < k:
			if abs(arr[0] - median) > abs(arr[-1] - median):
				ans.append(arr[0])
				arr.pop(0)
			else:
				ans.append(arr[-1])
				arr.pop()
			count += 1
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		median = arr[(len(arr) - 1) // 2]
		count = 0
		arry = []
		while arr and len(arry) < k:
			if arr[-1] - median >= median - arr[0]:
				arry.append(arr[-1])
				del arr[-1]
			else:
				arry.append(arr[0])
				del arr[0]
		return arry


class Solution:

	def getStrongest2(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		m = arr[(len(arr) - 1) // 2]
		dp = [[float('inf') for i in range(len(arr))] for i in range(len(arr))]
		for i in range(len(arr)):
			for j in range(len(arr)):
				if abs(arr[i] - m) > abs(arr[j] - m):
					strong = arr[i]
				elif abs(arr[i] - m) == abs(arr[j] - m):
					strong = arr[i] if arr[i] > arr[j] else arr[j]
				else:
					strong = arr[j]
				dp[i][j] = strong
		for line in dp:
			print(line)
		print()

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		med = sorted(arr)[(len(arr) - 1) // 2]
		return sorted(arr, key=lambda x: (abs(x - med), x))[-k:]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		x = sorted(arr)
		m = x[int((len(x) - 1) / 2)]
		i = 0
		j = len(arr) - 1
		strong = []
		while i <= j:
			if abs(x[i] - m) <= abs(x[j] - m):
				strong.append(x[j])
				j -= 1
			else:
				strong.append(x[i])
				i += 1
		return strong[:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		arr = sorted(arr)
		med_idx = (n - 1) // 2
		med_val = arr[med_idx]
		dist = []
		for i in range(len(arr)):
			dist.append((abs(arr[i] - med_val), arr[i], i))
		dist.sort(key=lambda x: (x[0], x[1]), reverse=True)
		ans = []
		for i in range(len(dist)):
			if i == k:
				break
			ans.append(arr[dist[i][2]])
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		if not k or not arr:
			return []
		arr = sorted(arr)
		m = arr[(len(arr) - 1) // 2]
		l = 0
		r = len(arr) - 1
		ans = []
		while k > 0 and l <= r:
			if abs(arr[l] - m) > abs(arr[r] - m):
				ans.append(arr[l])
				l += 1
			elif abs(arr[l] - m) == abs(arr[r] - m):
				if arr[l] > arr[r]:
					ans.append(arr[l])
					l += 1
				else:
					ans.append(arr[r])
					r -= 1
			else:
				ans.append(arr[r])
				r -= 1
			k -= 1
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		temp = list(arr)
		temp.sort()
		median = 0
		median = temp[(len(temp) - 1) // 2]
		l = 0
		r = len(arr) - 1
		res = []
		while k > 0:
			if median - temp[l] <= temp[r] - median:
				res.append(temp[r])
				r -= 1
			else:
				res.append(temp[l])
				l += 1
			k -= 1
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		arr.sort()
		m = arr[(n - 1) // 2]
		res = []
		l = 0
		r = n - 1
		while k > 0:
			c1 = abs(arr[l] - m)
			c2 = abs(arr[r] - m)
			if c1 > c2:
				res.append(arr[l])
				l += 1
			else:
				res.append(arr[r])
				r -= 1
			k -= 1
		return res


class Solution:

	def getStrongest(self, arr, k):
		n = len(arr)
		arr = sorted(arr)
		m = arr[(n - 1) // 2]
		(i, j) = (0, n - 1)
		while k > 0:
			if arr[j] - m >= m - arr[i]:
				j -= 1
			else:
				i += 1
			k -= 1
		return arr[:i] + arr[j + 1:]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		a = arr
		a.sort()
		n = len(a)
		m = a[n - 1 >> 1]
		ans = []
		(l, h) = (0, n - 1)
		while len(ans) < k:
			if abs(a[l] - m) > abs(a[h] - m):
				ans.append(a[l])
				l += 1
			elif abs(a[l] - m) < abs(a[h] - m):
				ans.append(a[h])
				h -= 1
			elif a[l] >= a[h]:
				ans.append(a[l])
				l += 1
			else:
				ans.append(a[h])
				h -= 1
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		n = len(arr)
		m = arr[int((n - 1) / 2)]
		result = []
		(l, r) = (0, n - 1)
		count = 0
		while l <= r and len(result) < k:
			if abs(arr[r] - m) > abs(arr[l] - m):
				result.append(arr[r])
				r -= 1
			elif abs(arr[l] - m) > abs(arr[r] - m):
				result.append(arr[l])
				l += 1
			else:
				result.append(arr[r])
				r -= 1
		return result


from collections import defaultdict, deque, Counter
from typing import List
import math
import copy
import random
import numpy as np
import bisect
import inspect
import unittest

def cmp(e1, e2):
	if e1[0] > e2[0] or (e1[0] == e2[0] and e1[1] > e2[1]):
		return 1
	elif e1[0] == e2[0] and e1[1] == e2[1]:
		return 0
	else:
		return -1

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr = sorted(arr)
		(i, j) = (0, len(arr) - 1)
		median = arr[j // 2]
		res = []
		while len(res) < k:
			if abs(arr[j] - median) >= abs(median - arr[i]):
				res.append(arr[j])
				j -= 1
			else:
				res.append(arr[i])
				i += 1
		return res

	def getStrongest1(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		assert n >= k
		if k == 0:
			return []
		if k == n:
			return arr
		kth = n - (n - 1) // 2
		median = self.findKthMax(arr, kth, cmp=lambda x, y: x - y)
		new_arr = [(abs(e - median), e) for e in arr]
		kmax = self.findKthMax(new_arr, k, cmp)
		res = []
		t = []
		for (x, y) in new_arr:
			if cmp((x, y), kmax) > 0:
				res.append(y)
			if cmp((x, y), kmax) == 0:
				t.append(y)
		if len(res) == k:
			return res
		else:
			return res + [t[0]] * (k - len(res))

	def findKthMax(self, l, k, cmp):
		if k > len(l):
			return None
		key = np.random.randint(0, len(l))
		keyv = l[key]
		sl = [i for i in l[:key] + l[key + 1:] if cmp(i, keyv) < 0]
		bl = [i for i in l[:key] + l[key + 1:] if cmp(i, keyv) >= 0]
		if len(bl) == k - 1:
			return keyv
		elif len(bl) >= k:
			return self.findKthMax(bl, k, cmp)
		else:
			return self.findKthMax(sl, k - len(bl) - 1, cmp)

def __starting_point():
	s = Solution()
	arr = [6, -3, 7, 2, 11]
	k = 3
	print(s.getStrongest(arr, k))
__starting_point()


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		back = arr[:]
		n = len(arr)
		med = arr[(n - 1) // 2]
		ans = []
		for i in range(n):
			arr[i] = abs(arr[i] - med)
		(l, r) = (0, n - 1)
		while l <= r and len(ans) < k:
			if arr[l] < arr[r]:
				ans += [back[r]]
				r -= 1
			elif arr[l] > arr[r]:
				ans += [back[l]]
				l += 1
			else:
				ans += [back[r]]
				r -= 1
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		median = arr[(len(arr) - 1) // 2]
		strength = sorted(arr, key=lambda x: (abs(x - median), x), reverse=True)
		return [i for i in strength[:k]]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		m = arr[(len(arr) - 1) // 2]
		(temp, res) = ([], [])
		for i in range(len(arr)):
			temp.append(abs(arr[i] - m))
		zipped_pairs = zip(temp, arr)
		z = [x for (_, x) in sorted(zipped_pairs)]
		return z[len(z) - k:]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		if len(arr) <= k:
			return arr
		arr.sort()
		median = arr[(len(arr) - 1) // 2]
		i = 0
		j = len(arr) - 1
		result = []
		while k > 0:
			if self.isStronger(arr[i], arr[j], median):
				result.append(arr[i])
				i += 1
			else:
				result.append(arr[j])
				j -= 1
			k -= 1
		return result

	def isStronger(self, a, b, median):
		return abs(a - median) > abs(b - median) or (abs(a - median) == abs(b - median) and a > b)


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		median = arr[(len(arr) - 1) // 2]
		list = []
		i = 0
		j = len(arr) - 1
		while i <= j and k > 0:
			if abs(arr[i] - median) > abs(arr[j] - median):
				list.append(arr[i])
				i += 1
			else:
				list.append(arr[j])
				j -= 1
			k -= 1
		return list


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		import numpy as np
		arr.sort()
		m = arr[int((len(arr) - 1) / 2)]
		a = sorted(arr, key=lambda x: (abs(x - m), x), reverse=True)
		return a[:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		m = arr[(len(arr) - 1) // 2]
		l = []
		i = 0
		j = len(arr) - 1
		while i <= j:
			if abs(arr[i] - m) > abs(arr[j] - m):
				l.append(arr[i])
				i = i + 1
			elif abs(arr[i] - m) <= abs(arr[j] - m):
				l.append(arr[j])
				j = j - 1
			if len(l) == k:
				return l


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr = sorted(arr)
		self.median = arr[(len(arr) - 1) // 2]
		count = 1
		(i, j) = (0, len(arr) - 1)
		values = []
		while count <= k:
			if self.key_func(arr[i]) > self.key_func(arr[j]):
				values.append(arr[i])
				i += 1
			elif self.key_func(arr[i]) < self.key_func(arr[j]):
				values.append(arr[j])
				j -= 1
			elif arr[i] > arr[j]:
				values.append(arr[i])
				i += 1
			else:
				values.append(arr[j])
				j -= 1
			count += 1
		return values

	def key_func(self, elem):
		return abs(elem - self.median)


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		sorted_arr = sorted(arr)
		n = len(arr)
		median = sorted_arr[(n - 1) // 2]
		results = []
		(start_idx, end_idx) = (0, n - 1)
		while k > 0 and start_idx <= end_idx:
			if abs(sorted_arr[start_idx] - median) < abs(sorted_arr[end_idx] - median):
				results.append(sorted_arr[end_idx])
				end_idx -= 1
			elif abs(sorted_arr[start_idx] - median) > abs(sorted_arr[end_idx] - median):
				results.append(sorted_arr[start_idx])
				start_idx += 1
			elif sorted_arr[start_idx] > sorted_arr[end_idx]:
				results.append(sorted_arr[start_idx])
				start_idx += 1
			else:
				results.append(sorted_arr[end_idx])
				end_idx -= 1
			k -= 1
		return results


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		sort = sorted(arr)
		m = sort[int((len(arr) - 1) / 2)]
		sort.reverse()
		sorted_by_m = sorted(sort, key=lambda x: abs(x - m), reverse=True)
		print(m, sorted_by_m)
		return sorted_by_m[:k]


class Solution:

	def getStrongest(self, A: List[int], k: int) -> List[int]:
		A.sort()
		z = []
		if len(A) % 2 == 1:
			n = A[(len(A) - 1) // 2]
		else:
			n = A[len(A) // 2 - 1]
		for i in A:
			z.append([abs(i - n), i])
		z.sort(key=lambda x: x[0])
		x = [j for (i, j) in z]
		return x[len(x) - k:]


class Solution:

	def getStrongest1(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		m = arr[(len(arr) - 1) // 2]
		d = {}
		for i in range(len(arr) - 1, -1, -1):
			tmp = abs(arr[i] - m)
			d.setdefault(tmp, [])
			d[tmp].append(arr[i])
		res = []
		for key in sorted(d.keys(), reverse=True):
			res.extend(d[key])
			if len(res) >= k:
				break
		return res[:k]

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		la = len(arr)
		m = arr[(la - 1) // 2]
		(i, j, res) = (0, la - 1, [])
		while len(res) < k:
			rt = abs(arr[j] - m)
			lt = abs(arr[i] - m)
			if rt == lt or rt > lt:
				res.append(arr[j])
				j -= 1
			else:
				res.append(arr[i])
				i += 1
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr = sorted(arr)
		K = len(arr)
		median = arr[(K - 1) // 2]
		(left, right) = (0, len(arr) - 1)
		ans = []
		print((arr, median))
		while left <= right and k > 0:
			if abs(arr[left] - median) <= abs(arr[right] - median):
				ans.append(arr[right])
				right -= 1
			else:
				ans.append(arr[left])
				left += 1
			k -= 1
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		l = len(arr)
		s = sorted(arr)
		middle = (l - 1) // 2
		median = s[middle]
		distances = []
		for i in s:
			distances.append([abs(i - median), i])
		strong_sort = sorted(distances, key=lambda x: x[0])
		s = l - k
		res = [strong_sort[i][1] for i in range(s, l)]
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		if not arr:
			return []
		elif len(arr) <= k:
			return arr
		arr.sort()
		n = len(arr)
		median = arr[int((n - 1) / 2)]
		arr = [(abs(i - median), i) for i in arr]
		arr.sort(reverse=True)
		return [i[1] for i in arr[:k]]


class Solution:

	def _get_median(self, arr):
		mid = int((len(arr) - 1) / 2)
		return arr[mid]

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr = sorted(arr)
		median = self._get_median(arr)
		arr = sorted([(abs(x - median), x) for x in arr], reverse=True)[:k]
		return [x for (rank, x) in arr]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		arr = sorted(arr)
		mid = arr[(n - 1) // 2]

		def mykey(x):
			return (abs(x - mid), x)
		arr = sorted(arr, key=lambda x: (abs(x - mid), x))
		return arr[n - k:]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr = sorted(arr)
		m = arr[(len(arr) - 1) // 2]
		power = [abs(x - m) for x in arr]
		order = sorted(zip(power, arr), reverse=True)
		return [order[i][1] for i in range(k)]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		m = arr[(len(arr) - 1) // 2]
		strongs = []
		for num in arr:
			strongs.append((abs(num - m), num))
		strongs.sort(reverse=True)
		return [x[1] for x in strongs[:k]]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		result = []
		left = 0
		right = len(arr) - 1
		arr.sort()
		m = arr[(len(arr) - 1) // 2]
		while left <= right:
			m_left = abs(m - arr[left])
			m_right = abs(m - arr[right])
			if m_left < m_right:
				result.append(arr[right])
				right -= 1
			elif m_left > m_right:
				result.append(arr[left])
				left += 1
			elif arr[left] > arr[right]:
				result.append(arr[left])
				left += 1
			else:
				result.append(arr[right])
				right -= 1
		return result[0:k]


from heapq import heappush, heappushpop

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		nums = sorted([x for x in arr])
		median = nums[(n - 1) // 2]
		heap = []
		for i in range(n):
			if len(heap) < k:
				heappush(heap, (abs(arr[i] - median), arr[i]))
			elif abs(arr[i] - median) >= heap[0][0]:
				heappushpop(heap, (abs(arr[i] - median), arr[i]))
		return [x[1] for x in heap]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		if len(arr) == 1 and k == 1:
			return arr
		ans = []
		arr.sort()
		m = arr[(len(arr) - 1) // 2]
		(i, j) = (0, len(arr) - 1)
		while i <= j:
			if abs(arr[j] - m) >= abs(arr[i] - m):
				ans.append(arr[j])
				j -= 1
			else:
				ans.append(arr[i])
				i += 1
		print(ans)
		return ans[:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr = sorted(arr)
		m = (len(arr) - 1) // 2
		mv = arr[m]
		ans = []
		(i, j) = (0, len(arr) - 1)
		while k and i <= j:
			(rv, lv) = (abs(arr[j] - mv), abs(arr[i] - mv))
			if rv > lv:
				ans.append(arr[j])
				j -= 1
				k -= 1
			elif lv > rv:
				ans.append(arr[i])
				i += 1
				k -= 1
			elif arr[j] > arr[i]:
				ans.append(arr[j])
				j -= 1
				k -= 1
			else:
				ans.append(arr[i])
				i += 1
				k -= 1
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		return sorted(arr, key=lambda num: (abs(num - arr[(len(arr) - 1) // 2]), num))[-k:]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		orderarr = sorted(arr)
		index = (len(arr) - 1) // 2
		mid = orderarr[index]
		dic = defaultdict(list)
		for i in range(len(orderarr) - 1, -1, -1):
			curabs = abs(orderarr[i] - mid)
			dic[curabs].append(orderarr[i])
		res = []
		keys = sorted(dic.keys())
		for i in range(len(keys) - 1, -1, -1):
			for j in dic[keys[i]]:
				res.append(j)
				if len(res) == k:
					return res
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		m = arr[(len(arr) - 1) // 2]
		(l, r) = (0, len(arr) - 1)
		ret = []
		while k > 0 and l <= r:
			print((l, r))
			(al, ar) = (abs(arr[l] - m), abs(arr[r] - m))
			if al == ar:
				if arr[l] >= arr[r]:
					ret.append(arr[l])
					l += 1
				else:
					ret.append(arr[r])
					r -= 1
			elif al > ar:
				ret.append(arr[l])
				l += 1
			else:
				ret.append(arr[r])
				r -= 1
			k -= 1
		return ret


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		heap = []
		sorted_arr = sorted(arr)
		m = sorted_arr[(len(arr) - 1) // 2]
		for num in arr:
			diff = abs(num - m)
			if len(heap) == k:
				heapq.heappushpop(heap, (diff, num))
			else:
				heapq.heappush(heap, (diff, num))
		return (n for (d, n) in heap)


import math

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		print(len(arr))
		m = arr[math.ceil(len(arr) / 2) - 1]
		print(m)
		n = len(arr)
		for i in range(n):
			arr[i] = [abs(arr[i] - m), arr[i]]
		arr.sort(reverse=True)
		arr = arr[:k]
		for i in range(k):
			arr[i] = arr[i][1]
		return arr


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		sort_arr = sorted(arr)
		n = len(arr)
		m = sort_arr[(n - 1) // 2]
		result = sorted(sort_arr, key=lambda x: [abs(x - m), x], reverse=True)
		return result[0:k]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		m = arr[(len(arr) - 1) // 2]
		return heapq.nlargest(k, [n for n in arr[::-1]], key=lambda x: abs(x - m))


import heapq

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		median = (len(arr) - 1) // 2
		new_arr = [(abs(arr[median] - arr[0]), arr[0])]
		heapq.heapify(new_arr)
		for i in range(1, len(arr)):
			if len(new_arr) < k:
				heapq.heappush(new_arr, (abs(arr[median] - arr[i]), arr[i]))
			else:
				heapq.heappushpop(new_arr, (abs(arr[median] - arr[i]), arr[i]))
		final_arr = []
		for i in range(len(new_arr)):
			final_arr.append(new_arr[i][1])
		return final_arr


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		n = len(arr)
		res = []
		median = arr[(n - 1) // 2]
		l = []
		arr.reverse()
		for i in range(n):
			l.append([arr[i], abs(median - arr[i])])
		l.sort(reverse=True, key=lambda x: x[1])
		i = 0
		while i < k - 1 or (i < n - 1 and l[i][1] == l[i + 1][1]):
			res.append(l[i][0])
			i += 1
		res.append(l[i][0])
		return res[:k]


def median(arr: List[int]) -> int:
	arr.sort()
	m = int((len(arr) - 1) / 2)
	return arr[m]

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		m = median(arr)
		strength = [abs(x - m) for x in arr]
		zipped = list(zip(strength, arr))
		zipped.sort(key=lambda x: (x[0], x[1]))
		return [x[1] for x in zipped[len(arr) - k:]]


import heapq

class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		n = len(arr)
		if n % 2 == 1:
			m = arr[n // 2]
		else:
			m = arr[n // 2 - 1]
		ans = []
		q = [(-abs(arr[i] - m), -i) for i in range(n)]
		heapq.heapify(q)
		for _ in range(k):
			ans.append(arr[-heapq.heappop(q)[1]])
		return ans


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		mean = arr[(len(arr) - 1) // 2]
		arr2 = list(map(lambda x: abs(x - mean), arr))
		arr3 = list(zip(arr, arr2))
		arr4 = sorted(arr3, key=lambda kv: (-kv[1], -kv[0]))
		return [arr4[i][0] for i in range(0, k)]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		n = len(arr)
		m = arr[(n - 1) // 2]
		res = []
		(l, r) = (0, n - 1)
		for i in range(k):
			if abs(arr[r] - m) >= abs(arr[l] - m):
				res.append(arr[r])
				r -= 1
			else:
				res.append(arr[l])
				l += 1
		return res


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		n = len(arr)
		median = sorted(arr)[(n - 1) // 2]
		arr_pair = [(x, abs(x - median)) for x in arr]
		arr_pair.sort(key=lambda x: (x[1], x[0]))
		return [x[0] for x in arr_pair[-k:]]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		ls = len(arr)
		arr.sort()
		median = arr[(ls - 1) // 2]
		print(median)
		res = []
		i = 0
		for num in arr:
			if i == k:
				heapq.heappush(res, (abs(num - median), num))
				heapq.heappop(res)
			else:
				heapq.heappush(res, (abs(num - median), num))
				i += 1
		return [x[1] for x in res]


class Solution:

	def getStrongest(self, l: List[int], k: int) -> List[int]:
		l.sort()
		m = l[(len(l) - 1) // 2]

		def fun(a, b):
			if abs(a - m) < abs(b - m):
				return 1
			elif abs(a - m) > abs(b - m):
				return -1
			else:
				return -1
		l = sorted(l, key=cmp_to_key(fun))
		l1 = []
		for i in range(k):
			l1.append(l[i])
		return l1


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		m = sorted(arr)[(len(arr) - 1) // 2]
		return [-x for (_, x) in sorted(((-abs(x - m), -x) for x in arr))[:k]]


class Solution:

	def getStrongest(self, arr: List[int], k: int) -> List[int]:
		arr.sort()
		med = arr[(len(arr) - 1) // 2]
		heap = []
		for a in arr:
			strength = abs(a - med)
			if len(heap) == k:
				heappushpop(heap, (strength, a))
			else:
				heappush(heap, (strength, a))
		return [a for (_, a) in heap]