1968. Array With Elements Not Equal to Average of Neighbors

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        m = (n + 1) >> 1
        res = []
        for i in range(m):
            res.append(nums[i])
            if i + m < n:
                res.append(nums[i + m])
        return res