<p>Given an integer array <code>num</code> sorted in non-decreasing order.</p>

<p>You can perform the following operation any number of times:</p>

<ul>
	<li>Choose <strong>two</strong> indices, <code>i</code> and <code>j</code>, where <code>nums[i] &lt; nums[j]</code>.</li>
	<li>Then, remove the elements at indices <code>i</code> and <code>j</code> from <code>nums</code>. The remaining elements retain their original order, and the array is re-indexed.</li>
</ul>

<p>Return the <strong>minimum</strong> length of <code>nums</code> after applying the operation zero or more times.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

<p><img src="https://assets.leetcode.com/uploads/2024/05/18/tcase1.gif" style="width: 160px; height: 70px;" /></p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,2,2,3,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

<p><img src="https://assets.leetcode.com/uploads/2024/05/19/tcase2.gif" style="width: 240px; height: 70px;" /></p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1000000000,1000000000]</span></p>

<p><strong>Output:</strong> <span class="example-io">2</span></p>

<p><strong>Explanation:</strong></p>

<p>Since both numbers are equal, they cannot be removed.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [2,3,4,4,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">1</span></p>

<p><strong>Explanation:</strong></p>

<p><img src="https://assets.leetcode.com/uploads/2024/05/19/tcase3.gif" style="width: 210px; height: 70px;" /></p>
</div>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>nums</code> is sorted in <strong>non-decreasing</strong> order.</li>
</ul>

class Solution:
    def minLengthAfterRemovals(self, nums: List[int]) -> int:
        # Approach 2: specific to this nums[i] < nums[j] condition.
        # 1. If the majority element (K) takes up over the half, then this element must be left. The answer is len(nums) - (len(nums) - K) * 2 = 2K - len(nums).
        # 2. Otherwise, assume that the highest frequency is a, the second one is b, and the others are c.
        # a < len(nums) // 2, then b + c >= H and b < H, then b - c <= 2b - H <= 2a - H < 2a - a = a.
        # Then we have a - (b - c), c, c after pairing from a and b.
        # Next, distribute a with b and c, until a is distributed out.
        # Then the diff for b and c must <= 1.
        # a - (b - c) = a - b + c < b + c - b + c = 2c, hence a must be distirbuted out.
        maj = nums[len(nums) // 2]
        k = 1
        for i in range(len(nums) // 2 - 1, -1, -1):
            if nums[i] == maj:
                k += 1
            else:
                break
        for i in range(len(nums) // 2 + 1, len(nums)):
            if nums[i] == maj:
                k += 1
            else:
                break
        if k > len(nums) // 2:
            return 2 * k - len(nums)
        else:
            return len(nums) % 2
29700