<p>You are given an integer array <code>nums</code> and an integer <code>k</code>. Append <code>k</code> <strong>unique positive</strong> integers that do <strong>not</strong> appear in <code>nums</code> to <code>nums</code> such that the resulting total sum is <strong>minimum</strong>.</p>

<p>Return<em> the sum of the</em> <code>k</code> <em>integers appended to</em> <code>nums</code>.</p>

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

<pre>
<strong>Input:</strong> nums = [1,4,25,10,25], k = 2
<strong>Output:</strong> 5
<strong>Explanation:</strong> The two unique positive integers that do not appear in nums which we append are 2 and 3.
The resulting sum of nums is 1 + 4 + 25 + 10 + 25 + 2 + 3 = 70, which is the minimum.
The sum of the two integers appended is 2 + 3 = 5, so we return 5.</pre>

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

<pre>
<strong>Input:</strong> nums = [5,6], k = 6
<strong>Output:</strong> 25
<strong>Explanation:</strong> The six unique positive integers that do not appear in nums which we append are 1, 2, 3, 4, 7, and 8.
The resulting sum of nums is 5 + 6 + 1 + 2 + 3 + 4 + 7 + 8 = 36, which is the minimum. 
The sum of the six integers appended is 1 + 2 + 3 + 4 + 7 + 8 = 25, so we return 25.
</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>
	<li><code>1 &lt;= k &lt;= 10<sup>8</sup></code></li>
</ul>

"""
So the minimum sum part just means I'm going to want to start at 1 and keep trying values
that are not in nums.

The tricky part is that with k being up to 10**8

So we use the arithmetic sum of two numbers and sort the original nums array first 
and kep taking the arithemetic sum between indexes until I have all k.

n // 2 *(2a + (n-1)*d)
here d == 1

"""
class Solution:
    def minimalKSum(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = 0
        found = 0
        idx = 1

        # handle 1 --> nums[0]
        if nums[0] != 1:
            diff = min(nums[0] - 1, k - found)
            ans += diff*( 2 + (diff - 1) ) // 2
            found += diff

        while idx < len(nums) and found < k:
            if nums[idx] - nums[idx-1] >= 2:
                diff = min(nums[idx] - nums[idx-1] - 1, k - found)
                # Want to start at first value greater than nums[idx-1]
                # so the n-1 cancels with the nums[idx-1] + 1 
                ans += diff*( 2*(nums[idx-1]+1) + (diff - 1) ) // 2
                found += diff
                print(diff, idx, ans, found)
            idx += 1

        # handle nums[-1] --> k
        if found != k:
            diff = k - found
            ans += diff*( 2*(nums[idx-1]+1) + (diff - 1) ) // 2

            print(diff, idx, ans)

        return ans 






""" graveyard
# TLE
        nums = set(nums)
        val = 1
        ans = 0
        while k:
            if val not in nums: 
                ans += val
                k -= 1
            val += 1
        return ans


 # MLE
 lhs = set(nums)
        rhs = set()
        prev_size = 0
        val = 1
        
        while len(rhs) < k:
            rhs |= set(range(val, val+k+1)) - lhs
            delta = len(rhs) - prev_size 
            prev_size = len(rhs)
            val += k + 1
            k -= delta
        
        print(rhs)
        return sum(rhs)


        

"""
581