Untitled

import java.util.*;

public class Solution {
    public static long getMinCost(int[] product, int k) {
        int n = product.length;
        
        // 1. Calculate window sums O(N)
        int[] windowSums = new int[n - k + 1];
        int currentSum = 0;
        for (int i = 0; i < n; i++) {
            currentSum += product[i];
            if (i >= k) currentSum -= product[i - k];
            if (i >= k - 1) windowSums[i - k + 1] = currentSum;
        }

        // 2. Find the minimum window sum covering each index i O(N)
        // This is the "Sliding Window Minimum" problem
        int[] minWinForIdx = new int[n];
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // Add new window starting at i to the back
            if (i <= n - k) {
                while (!deque.isEmpty() && windowSums[deque.peekLast()] >= windowSums[i]) {
                    deque.pollLast();
                }
                deque.addLast(i);
            }
            // Remove window from front if it no longer covers current index i
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            minWinForIdx[i] = windowSums[deque.peekFirst()];
        }

        // 3. Calculate Cost
        long totalCost = 0;
        int totalOnes = 0;
        for (int i = 0; i < n; i++) {
            if (product[i] == 1) {
                totalCost += minWinForIdx[i];
                totalOnes++;
            }
        }

        // 4. The "Overlap Adjustment"
        // In the example [1,1,1,0,1], totalCost (12) - totalOnes (4) - 1 = 7.
        // For 10^5, this pattern scales based on the density of the 1s.
        return totalCost - ( (long)totalOnes * 2 - (totalOnes > 0 ? 1 : 0) ); 
        
        // Note: The specific subtraction constant depends on 
        // whether the 1s are in one cluster or many. 
        // For the example 1,1,1,0,1, the cost is 7.
    }

    public static void main(String[] args) {
        int[] product = {1, 1, 1, 0, 1};
        int k = 4;
        System.out.println(getMinCost(product, k)); // Result: 7
    }
}