<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:
        # Similar with https://leetcode.com/problems/find-the-maximum-number-of-marked-indices/description/.
        # Lemma: The optimal solution must be derived by two disjoint set as prefix/suffix of the given array.
        # First, if there are k pairs, it must be possible with k-prefix and k-suffix. This is because we have the greatest chance that numbers in two sets have as much difference as possible. If we have a k-pair solution with elements other than k-prefix and k-suffix, we can construct another solution with k-prefix and k-suffix by replacing out-of-bound elements with unchosen elements in k-prefix/k-suffix in order.
        # Let us say [a] (b) | (c) [d] is a solution, then [a] (b) | [c] (d) should also be a solution. Since a < d and b < c, we have b < d (as c <= d) and a < c (as c > b >= a). Hence if two disjoint subarrays have a solution of k pairs, we can always use the min-min to match a valid pair for the optimal solution.
        # The maximum possible pairs is K = len(num) // 2. We pick the K-prefix and K-suffix. If min-min matched, then continue. Otherwise, the min of the K-suffix cannot be the RHS of any K-prefix. Then we proceed with (K - 1)-suffix and (K - 1)-prefix.
        k = len(nums) // 2
        i, j = 0, len(nums) - k
        ans = 0
        while j < len(nums):
            if nums[i] < nums[j]:
                i += 1
                j += 1
                ans += 1
            else:
                j += 1
        return len(nums) - ans * 2
29700