Rearrange an Array to Alternate Largest and Smallest Remaining Values

Given a list of integers, rearrange its elements so that they alternate between the extremes of what is left: the first element is the largest value, the second is the smallest, the third is the second largest, the fourth is the second smallest, and so on. Return the rearranged list. The report gives the ordering and the length bound only; this version also fixes the value range and how repeated values are handled. ### Function Signature ```python def alternate_max_min(values: list[int]) -> list[int]: ``` ### Rules - Build the output one element at a time from the elements not yet placed. Steps alternate, starting with a largest step: a largest step appends the largest remaining value, and a smallest step appends the smallest remaining value. Each step removes exactly one element. - Repeated values are separate elements. Removing one copy of a value leaves the other copies available for later steps. - When the length is odd, the final step is a largest step and appends the single element that is left. - Return a list of the same length that contains exactly the input's elements. Because equal values are interchangeable, the returned list is unique. - The input may be in any order. ### Constraints - `2 <= len(values) <= 10^4` - `-10^6 <= values[i] <= 10^6` - Values may be negative, zero or repeated. ### Examples **Example 1** ```text Input: values = [-1, 6, 3, 0, 9] Output: [9, -1, 6, 0, 3] ``` The largest value is 9 and the smallest is -1. Of what remains, the largest is 6 and the smallest is 0. The last remaining element, 3, is appended by the final largest step. **Example 2** ```text Input: values = [7, 7, 2, 7, 2, 5] Output: [7, 2, 7, 2, 7, 5] ``` The steps take one 7, one 2, a second 7 and the second 2. The remaining elements are 5 and 7, so the next largest step takes the last 7 and the final smallest step takes 5. **Example 3** ```text Input: values = [-8, 3] Output: [3, -8] ```