<p>You are given a <strong>0-indexed</strong> array of integers <code>nums</code> of length <code>n</code>, and two <strong>positive</strong> integers <code>k</code> and <code>dist</code>.</p>

<p>The <strong>cost</strong> of an array is the value of its <strong>first</strong> element. For example, the cost of <code>[1,2,3]</code> is <code>1</code> while the cost of <code>[3,4,1]</code> is <code>3</code>.</p>

<p>You need to divide <code>nums</code> into <code>k</code> <strong>disjoint contiguous </strong><span data-keyword="subarray-nonempty">subarrays</span>, such that the difference between the starting index of the <strong>second</strong> subarray and the starting index of the <code>kth</code> subarray should be <strong>less than or equal to</strong> <code>dist</code>. In other words, if you divide <code>nums</code> into the subarrays <code>nums[0..(i<sub>1</sub> - 1)], nums[i<sub>1</sub>..(i<sub>2</sub> - 1)], ..., nums[i<sub>k-1</sub>..(n - 1)]</code>, then <code>i<sub>k-1</sub> - i<sub>1</sub> &lt;= dist</code>.</p>

<p>Return <em>the <strong>minimum</strong> possible sum of the cost of these</em> <em>subarrays</em>.</p>

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

<pre>
<strong>Input:</strong> nums = [1,3,2,6,4,2], k = 3, dist = 3
<strong>Output:</strong> 5
<strong>Explanation:</strong> The best possible way to divide nums into 3 subarrays is: [1,3], [2,6,4], and [2]. This choice is valid because i<sub>k-1</sub> - i<sub>1</sub> is 5 - 2 = 3 which is equal to dist. The total cost is nums[0] + nums[2] + nums[5] which is 1 + 2 + 2 = 5.
It can be shown that there is no possible way to divide nums into 3 subarrays at a cost lower than 5.
</pre>

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

<pre>
<strong>Input:</strong> nums = [10,1,2,2,2,1], k = 4, dist = 3
<strong>Output:</strong> 15
<strong>Explanation:</strong> The best possible way to divide nums into 4 subarrays is: [10], [1], [2], and [2,2,1]. This choice is valid because i<sub>k-1</sub> - i<sub>1</sub> is 3 - 1 = 2 which is less than dist. The total cost is nums[0] + nums[1] + nums[2] + nums[3] which is 10 + 1 + 2 + 2 = 15.
The division [10], [1], [2,2,2], and [1] is not valid, because the difference between i<sub>k-1</sub> and i<sub>1</sub> is 5 - 1 = 4, which is greater than dist.
It can be shown that there is no possible way to divide nums into 4 subarrays at a cost lower than 15.
</pre>

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

<pre>
<strong>Input:</strong> nums = [10,8,18,9], k = 3, dist = 1
<strong>Output:</strong> 36
<strong>Explanation:</strong> The best possible way to divide nums into 4 subarrays is: [10], [8], and [18,9]. This choice is valid because i<sub>k-1</sub> - i<sub>1</sub> is 2 - 1 = 1 which is equal to dist.The total cost is nums[0] + nums[1] + nums[2] which is 10 + 8 + 18 = 36.
The division [10], [8,18], and [9] is not valid, because the difference between i<sub>k-1</sub> and i<sub>1</sub> is 3 - 1 = 2, which is greater than dist.
It can be shown that there is no possible way to divide nums into 3 subarrays at a cost lower than 36.
</pre>

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

<ul>
	<li><code>3 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>3 &lt;= k &lt;= n</code></li>
	<li><code>k - 2 &lt;= dist &lt;= n - 2</code></li>
</ul>

from sortedcontainers import SortedList

class Solution:
    def minimumCost(self, nums: List[int], k: int, dist: int) -> int:
        
        # Try to Understand Multiset Next time u visit This problem.
        # Also u can solve using Segment Tree ( coding mohan )
        # Segment Tree Solution is wonderful ( u will learn a lot)
        # Try to solve that solution 

        # ***************************************************************
        # The below Tow solution using 
        # SortedList + Sliding Window  O ( nlogn )

        # Coding Mohan Solution / Aryan Mittal Solution both are same

        n = len(nums)
        inf = 10**18
        ans = inf
        
        minK = SortedList()
        rest = SortedList()
        sum = 0
        
        for i in range(1, n):
            minK.add((nums[i], i))
            sum += nums[i]
            
            if len(minK) >= k:
                it = minK[-1]  # The largest element
                sum -= it[0]
                rest.add(it)
                minK.remove(it)
                
            if i - dist > 0:
                ans = min(ans, sum)
                
                to_remove = (nums[i - dist], i - dist)
                if to_remove in minK:
                    minK.remove(to_remove)
                    sum -= to_remove[0]
                    
                    if rest:
                        it = rest[0]  # The smallest element in rest
                        minK.add(it)
                        sum += it[0]
                        rest.remove(it)
                else:
                    rest.remove(to_remove)
        
        return ans + nums[0]

        # This is a Brilliant Solution only using one SortedList
        #  ( FROM DISCUSS )

        n = len(nums)
        sl = SortedList(nums[1 : 1 + dist])
        cursum, minsum = sum(sl[: k - 2]), float('inf')
        for i in range(1 + dist, n):
            if sl.bisect(nums[i]) <= k - 2:
                cursum += nums[i]
            else:
                cursum += sl[k - 2]
            minsum = min(minsum, cursum)
            sl.add(nums[i])
            if sl.bisect(nums[i - dist]) <= k - 2:
                cursum -= nums[i - dist]
            else:
                cursum -= sl[k - 2]
            sl.remove(nums[i - dist])
        return nums[0] + minsum

        # *******************************************************************
        # The below is using 2 HEAP and a SET 
        # NOT UDERSTANDED and also looked into BUT PASTING it to build this
        # Intuition and understand and code it in future if you visit
        # Very BEAUTIFUL Approach of using 2 HEAP PLZ PLZ TRY THIS NEXT TIME.
        # *******************************************************************

        # Length of the list
        n = len(nums)
        
        # To keep track of the cost
        minCostSum = float("inf")
        
        # MAX HEAP
        maxHeap = []
        
        # Sum of smallest "k - 2" values on right
        minRightSum = 0
        
        # A Set to keep track of the indices of "k-2" smallest elements
        indices = set()
        
        # To Keep the candidate values that might be useful later, we can use a minHeap
        minHeap = []
        
        for i in range(2,min(dist + 2,n)):
            
            # Push current value to the maxHeap
            heappush(maxHeap, [-nums[i], -i, i])
            
            # Update the sum
            minRightSum += nums[i]
            
            # Update the set
            indices.add(i)

            # If the heap size exceeds "k - 2"
            if len(indices) > k - 2:
                
                val,_,idx = heappop(maxHeap)
                
                # Push the data to the minHeap as it might be helpful later
                heappush(minHeap, [-val, idx, idx])
                
                # Update the sum
                minRightSum -= -val
                
                # Update the set
                indices.remove(idx)
                
        # Now, we can start the main logic
        # For the second subarray, the minimum possible valid starting index is "1"
        # And the maximum possible valid starting index is "n - (k - 2) - 1"
        for i in range(1, n - (k - 2)):
            
            # REMOVE INVALID DATA FROM BOTH HEAPS
            while maxHeap and maxHeap[0][2] not in indices: heappop(maxHeap)
            while minHeap and minHeap[0][2] <= i: heappop(minHeap)
                
            # Update the minCostSum
            minCostSum = min(minCostSum, nums[0] + nums[i] + minRightSum)
            
            # Now, we increment "i"
            # What if value at index "i + 1" is present in the maxHeap? 
            # When we increment "i" to "i + 1", the value needs to be removed from the maxHeap
            # How to check if value at index "i + 1" is present in the maxHeap?
            # We can use our set for that
            if i + 1 in indices:
                
                # Reduce the sum as we will remove this element
                minRightSum -= nums[i + 1]
                
                # Remove it from the set
                indices.remove(i + 1)
                
                # Since a value is reduced from the maxHeap, we can push a value from minHeap into maxHeap
                if minHeap: 
                    
                    top = heappop(minHeap)
                    heappush(maxHeap, [-top[0], -top[2], top[2]])
                    
                    # Update the set
                    indices.add(top[2])
                    
                    # Update the sum
                    minRightSum += top[0]

            # Since "i" is incremented in next iteration, for the last subarray, 
            # the maximum possible starting index is also increased by 1
            # So, we can push the value at index "i + 1 + dist" in the maxHeap
            # Only if it is a valid index
            if i + 1 + dist < n:
                
                heappush(maxHeap, [-nums[i + 1 + dist], -(i + 1 + dist), i + 1 + dist])

                # Update sum
                minRightSum += nums[i + 1 + dist]

                # Update the set
                indices.add(i + 1 + dist)

                # If the heap size becomes > (k -2)
                if len(indices) > k - 2:

                    # Pop the value on top
                    val,_,idx = heappop(maxHeap)
                    
                    # Push the data to the minHeap as it might be helpful later
                    heappush(minHeap, [-val, idx, idx])

                    # Update the sum
                    minRightSum -= -val

                    # Update the set
                    if idx in indices: indices.remove(idx)

        # Return the minimum possible cost
        return minCostSum





2351