Find Values Whose Removal Minimizes Pairing Cost

Problem Statement

You are given an array arr containing an odd number of integers n = 2m + 1.

You must remove exactly one element from arr. The remaining 2m integers must then be partitioned into m disjoint pairs (u_1, v_1), (u_2, v_2), ..., (u_m, v_m) such that the sum of absolute differences across all pairs,

cost = sum(|u_i - v_i| for i in 1..m)

is minimized.

Find all unique values in arr whose removal achieves the minimum possible optimal pairing cost. Return these values in ascending order.

Function Signature

def min_pairing_cost_removals(arr: list[int]) -> list[int]:
    pass

Input and Output Format

• Input: A list of integers arr of odd length n (1 <= n <= 2 * 10^5). Each element satisfies 1 <= arr[i] <= 10^9.
• Output: A list of unique integers sorted in ascending order representing every value whose removal yields the global minimum pairing cost.

Examples

Example 1

Input: arr = [4, 1, 5, 2, 8]
Output: [8]

Explanation: Sorting arr gives [1, 2, 4, 5, 8].

• Remove 1: remaining [2, 4, 5, 8], optimal pairs (2,4) and (5,8) give cost (4 - 2) + (8 - 5) = 2 + 3 = 5.
• Remove 4: remaining [1, 2, 5, 8], optimal pairs (1,2) and (5,8) give cost (2 - 1) + (8 - 5) = 1 + 3 = 4.
• Remove 8: remaining [1, 2, 4, 5], optimal pairs (1,2) and (4,5) give cost (2 - 1) + (5 - 4) = 1 + 1 = 2.

The minimum possible cost is 2, achieved only by removing 8.

Example 2

Input: arr = [1, 2, 3]
Output: [1, 3]

Explanation:

• Remove 1: remaining [2, 3], cost 1.
• Remove 2: remaining [1, 3], cost 2.
• Remove 3: remaining [1, 2], cost 1.

The minimum cost is 1, achieved by removing either 1 or 3.

Constraints

• 1 <= len(arr) <= 200,001
• len(arr) is always odd.
• 1 <= arr[i] <= 10^9 for all i.

Edge Cases

• len(arr) == 1: Removing the only element leaves 0 pairs; minimum cost is 0. Return [arr[0]].
• Duplicate elements: If multiple elements share the same value, removing any of their instances yields the same cost; include each such value only once in the result.