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

Difficulty: interview

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]:
        ## APPROACH : HEAP ##
        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()
        n = len(arr)
        m = arr[(n-1)//2]
        strong = []
        # for i in range(len(arr)):
        i,j = 0, len(arr)-1
        while i<=j:
            if abs(arr[i]-m) <= abs(arr[j]-m):
                strong.append(arr[j])
                j -= 1
            else:
                strong.append(arr[i])
                i += 1
        return(strong[:k])    
            


class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        # median = 0
        
        # if len(arr)%2 == 0:
        #     median = arr[int((len(arr)-1)/2)]
        # else:
        median = arr[int((len(arr)-1)/2)]
        strong = {}
        # print(median)
        
        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)
        # print(strong)
        strongest = []
        for x in strong:
            # if len(strongest) == k:
            #     break
            # else:
                # print(x)
            for val in sorted(x[1],reverse = True):
                if len(strongest) == k:
                    break
                # print(val)
                strongest.append(val)
                # if len(strongest) == k:
                #     break
        
        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))
        # temp.reverse()
        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))
        # print (sorted_diff)
        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)]
        # if len(arr) % 2 == 0:
        #     m = (arr[int(len(arr) / 2)] + arr[int(len(arr) / 2 - 1)]) / 2
        # else:
        #     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])

        # if valuearr[k-1][1] != valuearr[k][1]:
        #     res.append(valuearr[k-1][0])
        # else:
        #     if valuearr[k-1][0] > valuearr[k][0]:
        #         res.append(valuearr[k-1][0])
        #     else:
        #         res.append(valuearr[k][0])

        return res

class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        
        # Find median
        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])

        # Compute distance from median and sort
        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]:
        # get median of an array
        median = sorted(arr)[(len(arr) - 1) // 2]
        
        # initial sort
        arr.sort()
        
        # sort based on |arr[i] - median|
        arr.sort(key=lambda x: abs(x - median))
        
        return arr[(len(arr) - k):]

class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        '''
        1. find the median of the arr
        2. sort the list based on |arr[i]-m | > |arr[j] - m|
        3. select the top k strongest elements
        '''
        
        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]:
#         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
    
    # def getStrongest(self, arr: List[int], k: int) -> List[int]:
    #     m = sorted(arr)[(len(arr) - 1) // 2]
    #     return sorted(arr, reverse=True, key = lambda x: (abs(x - m), x))[:k]
    
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        m = arr[(len(arr) - 1) // 2]
        arr.sort(reverse=True, key=lambda x: (abs(x-m), x))
        return arr[:k]

class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        # assusing you cannot use the median function
        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:
\tdef getStrongest(self, arr: List[int], k: int) -> List[int]:
\t\tmedian = sorted(arr)[(len(arr)-1)//2]
\t\treturn 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]
        # easy to see that in the sorted array, if x is before y and smaller than the 
        # median, x is stronger than y, and likewise if y is after x and both are after the median, y is stronger than x.
        # so only need to check either end, since we know arr[0] and arr[N-1] are
        # the only candidates for 'strength'
        
        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: #rps >= lps. if equal we choose the right value
                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:
    # Time: O(n*log(n))
    # Space: O(n)
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        median = arr[(len(arr) - 1)//2]
        res, i, j = [], 0, len(arr) - 1
        while i <= j and k:
            if abs(arr[i] - median) > abs(arr[j] - median):
                res.append(arr[i])
                i += 1
            else:
                res.append(arr[j])
                j -= 1       
            k -= 1
        return res

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:
            # 3 cases - equality is a separate case
            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:
        # print(count,k)
        if strength[a] > strength[i]:
          ans.append(arr[a])
          a -= 1
        elif strength[a] < strength[i]:
          ans.append(arr[i])
          i += 1
        else:
          if 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]:
        
        ## Method 1
        # 计算median
        # 挨个计算绝对值，保存(key:abs,value:[num])
        # key[从大到小]，value从大到小。res到达k的长度，就return
        
        ## Method 2
        # 计算median
        # 在排过序的list中，找到最左和最右 对比他们的abs（x-median）
        # 如果abs一样，则比较他们的原本大小。
        # 不然大的那个丢进去，大的指针前进，小的指针留在原位
        # 直到k = 0
        
        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
        
        
        
        
        
        
        
        
        
#         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


class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        m = (len(arr) - 1) // 2
        i = 0
        j = len(arr) - 1

        result = []
        while i <= j and len(result) < k:
            if abs(arr[i] - arr[m]) > abs(arr[j] - arr[m]):
                result.append(arr[i])
                i += 1
            else:
                result.append(arr[j])
                j -= 1

        return result


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))
        #print (res)
        
        return [res[i][1] for i in range (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
    
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        m = sorted(arr)[(len(arr) - 1) // 2]
        return sorted(arr, reverse=True, key = lambda x: (abs(x - m), x))[:k]

from collections import defaultdict
class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        
        # 计算median
        # 挨个计算绝对值，保存(key:abs,value:[num])
        # key[从大到小]，value从大到小。res到达k的长度，就return
        
        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) 
        #mid = len(arr) // 2
        median = arr[(len(arr) - 1) // 2]
        #median = (sorted_array[length // 2] + sorted_array[(length-1)//2])/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]:
        arr.sort()
        m=arr[(len(arr)-1)//2]
        #print(m)
        return sorted(arr,key=lambda x:(abs(x-m),x),reverse=True)[: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]:
            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]:
        n=len(arr)
        arr=sorted(arr)
        m=-1
        if(n%2==0):
            m=arr[(n-1)//2]
        else:
            m=arr[n//2]
        # print(arr)
        # print(m)
        arr=sorted(arr,key=lambda x:(abs(x-m),x))
        # print(arr)
        return arr[-k:]

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

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(object):
    def sign(self, num):
        if num==0:
            return 0
        elif num>0:
            return 1
        else:
            return -1
    def getStrongest(self, arr, k):
        \"\"\"
        :type arr: List[int]
        :type k: int
        :rtype: List[int]
        \"\"\"
        #from numpy import sign
        arr=sorted(arr)
        le=len(arr)
        if le==0:
            return []
        median=arr[int((le-1)/2)]
        strong=sorted([(abs(median-l),self.sign(l-median)) for l in arr])[-k:]
        #print(median, [abs(median-l)+Solution.sign([],l-median) for l in arr], strong)
        return [median+boo*i for i, boo in strong]
        

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:
    # arr min 1 item
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        arr = sorted(arr)
        l = len(arr)
        
        # median = average of middle 2 if even
        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]:
        median = sorted(arr)[(len(arr) - 1) // 2]
        return heapq.nsmallest(k, arr, key=lambda x: (-abs(x-median), -x))

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]:
        n= len(arr)
        if k == n:
            return arr
        
        arr.sort()
        median = arr[(n-1)//2]
        
        left, right = 0, n-1
        ans = []
        while k > 0 and left <= right:
            if abs(arr[left]-median) > abs(arr[right]-median):
                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]:
        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]:
        
        #calc median
        sarr = sorted(arr)
        L = len(arr)
        
        if L / 2 % 1 == 0:
        #    median = (sarr[int(L/2)] + sarr[int(L/2)-1]) / 2
            median = sarr[int((L-1)/2)]
        else:
            median = sarr[int(L/2-.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]
        # print(x, median)
        jj = sorted(list(range(len(arr))), key=lambda y: (abs(arr[y]-median), arr[y]), reverse=True)
        # print(jj)
        # print([(abs(arr[x]-median), x) for x in jj])
        n = [arr[i] for i in jj]
        # print(n)
        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)
            
            #print(arr[-1],arr[0])
            #print(rv,lv)
            
            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()
#    if n%2:
#      median = ( arr[n//2] )
#    else:
#      median = ( arr[n//2] + arr[n//2-1] ) / 2
    median = arr[(n-1)//2]
    heap = [] # min 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]:
        median = sorted(arr)[(len(arr) - 1) // 2]
        
        # initial sort
        arr.sort()
        
        # sort based on |arr[i] - median|
        arr.sort(key=lambda x: abs(x - median))
        
        return arr[(len(arr) - k):]


class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        res = []
        i = 0
        j = len(arr) - 1
        if(j == 0):
            return arr
        median = arr[j//2]
        while len(res) < k:
            if(abs(median - arr[i]) <= abs(arr[j] - median)):
                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.sort()
        median = arr[(len(arr) - 1)//2]
        res, i, j = [], 0, len(arr) - 1
        while i <= j and k:
            if abs(arr[i] - median) > abs(arr[j] - median):
                res.append(arr[i])
                i += 1
            else:
                res.append(arr[j])
                j -= 1       
            k -= 1
        return res


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 = []
        #print(sorted_data)
        #while k != 0:
        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 = []
        # arr.remove(median)
        # arr = deque(arr)
        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 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
        ind=0
        while(ind<k):
            if(abs(arr[left]-m)>abs(arr[right]-m)):
                ans.append(arr[left])
                left+=1
            else:
                ans.append(arr[right])
                right-=1
            ind+=1
        return ans


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]:
        arr.sort()
        median = arr[(len(arr)-1)//2]
        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 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 abs(arr[-1] - median) >= abs(arr[0]- median) :
                arry.append(arr[-1])
                del arr[-1]
            else:
                arry.append(arr[0])
                del arr[0]
           
        return arry

class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        n = len(arr)
        m = arr[(n-1)//2]
        strong = []
        # for i in range(len(arr)):
        i,j = 0, len(arr)-1
        while i<=j:
            if abs(arr[i]-m) <= abs(arr[j]-m):
                strong.append(arr[j])
                j -= 1
            else:
                strong.append(arr[i])
                i += 1
        return(strong[: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]


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.nlargest(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]:
        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]:
        
        sarr = sorted(arr)
        L = len(arr)
        
        if L / 2 % 1 == 0:
            median = sarr[int((L-1)/2)]
        else:
            median = sarr[int(L/2-.5)]
        
            
        #absm = [abs(a - median) for a in arr]
        
        tarr = [[abs(arr[i] - median), 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]:
        arr.sort()
        median = arr[(len(arr)-1)//2]
        count = 0
        arry = []
        while arr and len(arry)<k:
            if abs(arr[0] - median) - abs(arr[-1]- median) >0:
                arry.append(arr[0])
                del arr[0]
            elif abs(arr[-1] - median) - abs(arr[0]- median) >0:
                arry.append(arr[-1])
                del arr[-1]
            elif abs(arr[-1] - median) == abs(arr[0]- median):
                if arr[-1] < arr[0]:
                    arry.append(arr[0])
                    del arr[0]
                else:
                    arry.append(arr[-1])
                    del arr[-1]
        return arry

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]:
        medVal = sorted(arr)[(len(arr)-1)//2]
        return sorted(arr, key = lambda x: [abs(x - medVal), x], reverse = True)[:k]
        
        '''
        sList = sorted(arr)
        medianIndex = (len(arr)-1) // 2
        medianValue = sList[medianIndex]
        
        strongList = [(abs(elem - medianValue), elem) for elem in sList]
        #finalList = sorted(strongList, reverse = True, key=lambda x:x[0])
        ht = {}
        returnList = []
        for elem in strongList:
            if elem[0] in ht:
                ht[elem[0]].append(elem[1])
            else:
                ht[elem[0]] = [elem[1]]
                
        for key in ht:
            curr = sorted(ht[key], reverse = True)
            returnList.append((key, curr))
 
        finalList = sorted(returnList, reverse = True, key=lambda x:x[0])
        newList = [elem[1] for elem in finalList]
        newerList = [i for elem in newList for i in elem]
        
        return newerList[:k]
        '''

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]:
        # K * n
        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: List[int], k: int) -> List[int]:
        ans = []
        arr.sort()
        lo, hi = 0, len(arr) - 1
        m = arr[hi // 2]

        while lo <= hi and len(ans) < k:
            if abs(arr[hi] - m) < abs(arr[lo] - m):
                ans.append(arr[lo])
                lo += 1
            else:
                ans.append(arr[hi])
                hi -= 1
        return ans

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
            else:
                if 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        
            


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

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))

    # all elements are same 算法会退化
    # 3-sets quicksort的实际实现
    # 标准算法尽量用标准库函数
    def findKthMax(self, l, k, cmp):
        if k > len(l):
            return None
        # 随机生成一个下标key,并获取下标对应的数组值keyv
        key = np.random.randint(0, len(l))
        keyv = l[key]

        # 遍历数组（刨除key），sl数组是小于keyv的值，bl数组是大于等于keyv的值
        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]

        # 如果bl的长度恰好是k-1,那么说明keyv就是第k大的数
        if len(bl) == k-1:
            return keyv
        # 如果bl的长度大于等于k,说明第k大的数在bl中，迭代findKthMax函数，找出bl中第k大的数
        elif len(bl) >= k:
            return self.findKthMax(bl, k, cmp)
        # 如果bl的长度小于k-1,说明第k大的数在sl中，因为bl中已经有len(bl)个比目标值大的数，加上keyv本身，所以要找出sl中第（k-len(bl)-1）大的数
        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()
        i = 0
        j = len(arr) - 1
        median = arr[(len(arr) - 1)//2]
        while len(arr) + i - j <= k:
            if median - arr[i] > arr[j] - median:
                i += 1
            else:
                j -= 1
                
        return arr[:i] + arr[j + 1:]


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

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]:
        ans = []
        arr.sort()
        lo, hi = 0, len(arr) - 1
        m = arr[hi // 2]

        while lo <= hi:
            if abs(arr[hi] - m) >= abs(arr[lo] - m):
                ans.append(arr[hi])
                hi -= 1
            else:
                ans.append(arr[lo])
                lo += 1
        return ans[:k]

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

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()
        n = len(arr)
        m = arr[(n-1)//2]
        strong = []
        # for i in range(len(arr)):
        i,j = 0, len(arr)-1
        while i<=j:
            if abs(arr[i]-m) <= abs(arr[j]-m):
                strong.append(arr[j])
                j -= 1
            else:
                strong.append(arr[i])
                i += 1
        return(strong[:k])

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


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

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


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))
        temp.reverse()
        return temp[:k]

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

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

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
        res = []
        while len(res) < k:
            if abs(arr[l] - m) > abs(arr[r] - m):
                res.append(arr[l])
                l = l + 1
            else:
                res.append(arr[r])
                r = r - 1
        return res

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]:
        arr.sort()
        i = 0
        j = len(arr) - 1
        median = arr[(len(arr) - 1)//2]
        while len(arr) + i - j <= k:
            if median - arr[i] > arr[j] - median:
                i += 1
            else:
                j -= 1
        return arr[:i] + arr[j + 1:] 

class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        import numpy as np
        arr.sort()
        #m=np.median(np.array(arr))
        m=arr[int((len(arr)-1)/2)]
        #sorted(arr, key=lambda x: (abs(x-median), x), reverse=True)[:k]
        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
            else:
                if 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
            else:
                if 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)]
        # sorted_by_m = {}
        # for n in sort:
        #     curr = abs(n - m)
        #     if curr in sorted_by_m:
        #         sorted_by_m.append(curr)
        #     else:
        #         sorted_by_m = [curr]
        
        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]:
        # sort, find median per definition
        # iterate backwards over sorted list
        # abs(diff from median) used as key in hashmap, with element as value
        # this naturally places larger values first in {key, [vals]}
        # starting from largest key, return K values
        # O(NlogN) time, O(N) space

        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]:
        # same initial strategy to find median
        # but afterward use two pointers to build up result list
        # terminating on K elements
        # O(NlogN) time, O(1) \"extra\" space not counting result list

        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, 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])
        z=z[::-1]
        x=[j for i,j in z]
        return x[:k]
            


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

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]:
        
        # get median
        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])
        #print(strong_sort)
        s = l - k
        #print(s)
        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 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=[]
        for i in z[len(z)-k:]:
            x.append(i[1])
        return x
            


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):
            # 自定义最强排序的key函数
            # 注意py 3不同于其他语言的传入两个参数的自定义比较函数
            # 此处的意思代表先按照abs升序排列, 相等情况下再按照自身的值的升序排列
            return (abs(x - mid), x)

        # 按照最强排序后取最后的k个即为所求
        #arr = sorted(arr, key=mykey)
        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]:
        n = len(arr)        
        arr.sort()        
        m = arr[((n-1)//2)]
        
        arr.sort(key=lambda x: (abs(x-m),x), reverse=True)
        
        return arr[:k]
#         index = []        
        
#         for i in range(n):
#             index.append([abs(arr[i]-m), i, arr[i]])
        
#         index.sort(key=lambda x: (x[0],x[1]), reverse=True)
    
#         res = []
#         for j in range(k):
#             res.append(index[j][2])
        
#         return res


class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        temp = sorted(arr)
        median = 0
        n = len(arr)
        median = temp[(n-1)//2]
        j = len(arr)-1
        i = 0
        res = []
        print(\"hi\",str(median))
        while i<=j:
            left = median - temp[i]
            right = temp[j] - median
            if left > right:
                res.append(temp[i])
                i+=1
            elif left < right:
                res.append(temp[j])
                j-=1
            else:
                if temp[i]>temp[j]:
                    res.append(temp[i])
                    i+=1
                else:
                    res.append(temp[j])
                    j-=1
            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]
        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]:
        m = sorted(arr)[(len(arr) - 1) // 2]
        return sorted(arr, key = lambda x: (-abs(x - m), -x))[: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
            else:
                if arr[left] > arr[right]:
                    result.append(arr[left])
                    left += 1 
                else:
                    result.append(arr[right])
                    right -= 1
            
        return result[0:k]
        
                
            
            
            


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


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]:
        m = sorted(arr)[(len(arr) - 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]:
        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]:
        sortedArr = sorted(arr)
        median = sortedArr[(len(sortedArr) - 1) // 2]
        strength = [[k, abs(k - median)] for k in sortedArr]
        strength = sorted(strength, key=lambda x: (x[1], x[0]), reverse=True)
        return [i[0] for i in strength[:k]]


#import heapq,heappush,heapop
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
            else:
                if 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()
#         # mean_index = (len(arr) - 1) // 2
#         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)]
        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]
        #print(m, arr)
        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))

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

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
        # print(l)
        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])
        # res.sort(reverse=True)
        # print(res)
        
        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()
        median = arr[(len(arr)-1)//2]
        #print(median)
        arr.sort(key = lambda x: (abs(x-median),x),reverse = True)
        #print(arr)
        return arr[:k]


class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        # mean_index = (len(arr) - 1) // 2
        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]:
        
        # Find median
        n =  len(arr)
        median = sorted(arr)[(n-1)//2]
        
        # Compute distance from median and sort
        arr_pair = [(i,abs(arr[i]-median)) for i in range(n)]
        arr_pair.sort(key=lambda x: (x[1],arr[x[0]]))
        return [arr[x[0]] for x in arr_pair[-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]:
        n = len(arr)
        median = sorted(arr)[(n-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]:
        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]:
        
        # Find median
        n =  len(arr)
        median = sorted(arr)[(n-1)//2]
        
        # Compute distance from median and sort
        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]:
        arr.sort()
        median = arr[(len(arr)-1)//2]
        ans,i,j = [],0,len(arr)-1
        if(len(arr) == 1):
            return arr
        
        while(i<=j and k>0):
            if(abs(arr[i]-median) > abs(arr[j]-median)):
                ans.append(arr[i])
                i +=1
            else:
                ans.append(arr[j])
                j-=1
            
            k -=1
        
        return ans

class Solution:
    def getStrongest(self, arr: List[int], k: int) -> List[int]:
        ls = len(arr)
        arr.sort()
        #median = (arr[ls//2] + arr[ls//2-1]) / 2 if ls % 2 == 0 else arr[ls//2]
        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, arr: List[int], k: int) -> List[int]:
        m = sorted(arr)[(len(arr) - 1) // 2]
        return sorted(arr, reverse=True, key = lambda x: (abs(x - m), x))[: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)
      if length==1:
        return arr
      ans = []
      arr.sort()
      strength = self.strengths(arr,length)
      count = 0
      i = 0
      a = length - 1
      while count < k and i != a:
        # print(count,k)
        if strength[a] > strength[i]:
          ans.append(arr[a])
          a -= 1
        elif strength[a] < strength[i]:
          ans.append(arr[i])
          i += 1
        else:
          if 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
        


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


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)
            # print(heap, strength, a)
            if len(heap) == k:
                heappushpop(heap, (strength, a))
            else:
                heappush(heap, (strength, a))
        return [a for _, a in heap]