Find Values Whose Removal Minimizes Pairing Cost

You are given an odd-length list of positive integers. Remove exactly one element, then partition every remaining element into pairs. The cost of a pair is the absolute difference of its two values, and the total cost is the sum over all pairs. For each possible removal, the remaining values are paired to minimize total cost. Implement: ```text optimal_removal_values(nums: List[int]) -> List[int] ``` Return the distinct values for which removing one occurrence yields the globally smallest pairing cost. Return all such values in increasing order, so the function does not impose an unsupported choice when several removals are equally good. ### Constraints - `1 <= len(nums) <= 200_001` - `len(nums)` is odd. - `1 <= nums[i] <= 10^9` - Every remaining element must appear in exactly one pair. - The target complexity is \(O(n\log n)\) time and \(O(n)\) extra space. ### Clarifications - Equal values at different positions are distinct removable elements, but the returned list contains each optimal value once. - For a one-element list, removing its only element leaves an empty pairing with cost zero, so return that value. - The function returns every optimal removed value, not an original index or the minimum cost. ```hint Sort and reuse adjacent-pair costs For an even sorted multiset, an optimal pairing uses adjacent values. Precompute compatible prefix and suffix costs so each removal does not require a new pairing pass. ``` ### Examples ```text Input: nums = [1, 3, 4] Output: [1] Explanation: Removing 1 leaves (3, 4) with cost 1, the global minimum. Input: nums = [1, 2, 3] Output: [1, 3] Explanation: Removing either endpoint leaves a pair with cost 1. Input: nums = [5] Output: [5] ``` ### Evaluation Focus - Proof of the adjacent-pair property after sorting. - Correct handling of the parity shift on each side of the removed element. - Collection of every tied optimal value, including duplicates in the input. - Avoidance of quadratic recomputation. ### Extension How would the problem change if exactly three elements had to be removed?