Leetcode 1968. Array With Elements Not Equal to Average of Neighbors

Rearrange a given array of distinct integers so that for every internal index i, nums[i] is not equal to the average of its neighbors — equivalently, no three consecutive elements form an arithmetic progression. Return any permutation satisfying this (n up to 1e5).