<p>You are given an integer array <code>nums</code>. In one operation, you can replace <strong>any</strong> element in <code>nums</code> with <strong>any</strong> integer.</p>

<p><code>nums</code> is considered <strong>continuous</strong> if both of the following conditions are fulfilled:</p>

<ul>
	<li>All elements in <code>nums</code> are <strong>unique</strong>.</li>
	<li>The difference between the <strong>maximum</strong> element and the <strong>minimum</strong> element in <code>nums</code> equals <code>nums.length - 1</code>.</li>
</ul>

<p>For example, <code>nums = [4, 2, 5, 3]</code> is <strong>continuous</strong>, but <code>nums = [1, 2, 3, 5, 6]</code> is <strong>not continuous</strong>.</p>

<p>Return <em>the <strong>minimum</strong> number of operations to make </em><code>nums</code><em> </em><strong><em>continuous</em></strong>.</p>

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

<pre>
<strong>Input:</strong> nums = [4,2,5,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong>&nbsp;nums is already continuous.
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,2,3,5,6]
<strong>Output:</strong> 1
<strong>Explanation:</strong>&nbsp;One possible solution is to change the last element to 4.
The resulting array is [1,2,3,5,4], which is continuous.
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,10,100,1000]
<strong>Output:</strong> 3
<strong>Explanation:</strong>&nbsp;One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is [1,2,3,4], which is continuous.
</pre>

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

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        # n elements in array
        # max - min = n - 1
        # so elements must be {min, min + 1, min + 2 ... max - 1, max} because there are max-min+1
        # elements here, and there are also n elements, so max-min+1 = n means n-1 = max-min. recall
        # we need elements to be unique
        n = len(nums)
        sorted_nums = sorted(set(nums))

        res = n
        for i in range(len(sorted_nums)):
            curr_min = sorted_nums[i]
            curr_max = curr_min + n - 1
            left, right = 0, len(sorted_nums) - 1
            while left < right - 1:
                mid = (left + right) // 2
                if sorted_nums[mid] > curr_max:
                    right = mid - 1
                else:
                    left = mid
            j = left
            if sorted_nums[right] <= curr_max:
                j = right
            # j is the largest index such that sorted_nums[k] <= curr_max for all k <= j
            # thus we know that there are j - i + 1 elements that lie in our desired range
            res = min(res, n - (j - i + 1))

        return res
                






















        # n = len(nums)
        # nums = [x for x in set(nums)]
        # nums = sorted(nums)

        # res = n - 1

        # for i in range(len(nums)):
        #     # assume that curr_min is the minimum of the final continuous array after
        #     # all operations are complete
        #     # so the maximum of the continuous array is curr_min + n - 1
        #     # so we get rid of all numbers strictly less than curr_min
        #     # and we get rid of all numbers larger than curr_min + n - 1
        #     # to do so, we find the index where curr_max should appear via binary search
        #     curr_min = nums[i]
        #     curr_max = curr_min + n - 1

        #     # find smallest index x such that nums[x] > curr_max
        #     left, right = i, len(nums) - 1
        #     while left < right - 1:
        #         mid = (left + right) // 2
        #         if nums[mid] <= curr_max:
        #             left = mid + 1
        #         else:
        #             right = mid
        #     if nums[left] > curr_max:
        #         x = left
        #     else:
        #         x = right
        #     if curr_max >= nums[-1]:
        #         x = len(nums)

        #     # number of unique numbers in array that lie in [curr_min, curr_max]
        #     num_unique = x - i

        #     # number of numbers that must be replaced
        #     num_replace = n - num_unique
            
        #     res = min(res, num_replace)
        # return res
1040