<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>

# /**
#  * 思路：
#  * 当且仅当两个元素不相等时，他们可以相互抵消
#  * 因为数组是非降序排列的，所以相等的元素都相邻
#  * 设 p 为数量最多的元素的个数，q 为其他元素的个数
#  * 如果 p >= q，则 q 对应的元素都会被抵消，则最终的数组长度 = p - q
#  * 如果 p < q，则首先能用 p 对应的元素抵消掉 p 个其他元素，每次抵消都选择数量最多的元素，最后会剩余 q - p 个元素
#  * 对于剩余的 q - p 个元素，可继续递归进行上述判断，最终可归纳得到：当 数组长度 为偶数时，所有的元素都会被抵消掉，为基数时，会剩余一个元素。证明过程略（其实是不会）
# 复杂度：O(N)
#  */

class Solution:
    def minLengthAfterRemovals(self, nums: List[int]) -> int:
        p = cur_p = 1
        size = len(nums)
        for i in range(1,size):
            if nums[i] == nums[i-1]:
                cur_p = cur_p + 1
                p = max(p, cur_p)
            else:
                cur_p = 1
        q = size - p
        return p - q if p >= q else (q - p) % 2
        
1033