<p>You are given a <strong>0-indexed</strong> array <code>nums</code> of <strong>distinct</strong> integers. You want to rearrange the elements in the array such that every element in the rearranged array is <strong>not</strong> equal to the <strong>average</strong> of its neighbors.</p>

<p>More formally, the rearranged array should have the property such that for every <code>i</code> in the range <code>1 &lt;= i &lt; nums.length - 1</code>, <code>(nums[i-1] + nums[i+1]) / 2</code> is <strong>not</strong> equal to <code>nums[i]</code>.</p>

<p>Return <em><strong>any</strong> rearrangement of </em><code>nums</code><em> that meets the requirements</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5]
<strong>Output:</strong> [1,2,4,5,3]
<strong>Explanation:</strong>
When i=1, nums[i] = 2, and the average of its neighbors is (1+4) / 2 = 2.5.
When i=2, nums[i] = 4, and the average of its neighbors is (2+5) / 2 = 3.5.
When i=3, nums[i] = 5, and the average of its neighbors is (4+3) / 2 = 3.5.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [6,2,0,9,7]
<strong>Output:</strong> [9,7,6,2,0]
<strong>Explanation:</strong>
When i=1, nums[i] = 7, and the average of its neighbors is (9+6) / 2 = 7.5.
When i=2, nums[i] = 6, and the average of its neighbors is (7+2) / 2 = 4.5.
When i=3, nums[i] = 2, and the average of its neighbors is (6+0) / 2 = 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        sorted_nums = sorted(nums)
        ans = sorted_nums.copy()
        if n % 2 :
            median = sorted_nums[n//2]
            # ans[n//2] = median


        else:
            median = (sorted_nums[n//2] + sorted_nums[(n-1)//2])/2
        k = 1
        for i in range(n):
            # print(sorted_nums[i], k)
            if k > n - 1:
                break 
            if sorted_nums[i] <= median:
                ans[k] = sorted_nums[i]
                k+=2
            
        k = 0
        for i in range(n):
            if k > n-1:
                break
            if sorted_nums[i] >= median:
                ans[k] = sorted_nums[i]
                k+=2
        # print(ans)
        return ans

        # print(median, ans[n//2], ans[(n-1)//2])
        
        # print(sorted_nums)
        k = 0
        for i in range(1,n,2):
            if isinstance(median, int):
                if i == n//2:
                    continue
            else:
                if i == n//2 or i == (n-1)//2:
                    continue
            ans[i] = sorted_nums[k]
            k+=1
        k = n//2 + 1    

        for i in range(0, n, 2):
            if isinstance(median, int):
                if i == n//2:
                    continue
            else:
                if i == n//2 or i == (n-1)//2:
                    continue
            
            # print(sorted_nums[i], sorted_nums[k])
            ans[i] = sorted_nums[k]
            k+=1
        # print(sorted_nums)
        # print(ans)
        return ans
        

1025