Problem Setter : Kamonasish Roy (Bullet)
Problem tag: Two pointer, Data structure, Sliding window technique
Tutorial (Prepared by Abid Hussen (Abid_52):
Approach:

1. Iterate Over All K-Length Subarrays:

   • Compute the sum of each K-length subarray and update the minimum answer (ans).

2. Optimize with a Swap:

   • For each K-length subarray, swap the maximum element in the subarray with
     the minimum element outside it.
   • Recalculate the subarray sum and update ans with the smaller value.

• use multiset to store maximum value of each K-length subarray.

3. Result:
   • The final answer is the smallest ans obtained.

Note : You can solve it using advanced data structures like Segment Tree, Sparse Table, or any RMQ, but this is not required for this problem.
Time Complexity: O(N log N).
Bonus : Try to solve it O(N).
Code :

#include<bits/stdc++.h>
using namespace std;
const long long M=2e5+10,MOD=1000000007;
typedef long long ll;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
    	multiset<ll>st;
    	int n,k;
    	cin>>n>>k;
    	ll ans=1e18;
    	vector<ll>a(n+1);
    	for(int i=1;i<=n;i++)cin>>a[i];
    	vector<ll>pr(n+2,1e9);
    	vector<ll>lr(n+2,1e9);
    	ll cur=1e9;
    	for(int i=1;i<=n;i++){
    		cur=min(cur,a[i]);
    		pr[i]=cur;
    		
    	}
    	cur=1e9;
    	for(int i=n;i>=1;i--){
    		cur=min(cur,a[i]);
    		lr[i]=cur;
    	}
    	ll sum=0;
    	int l=1;
    	for(int i=1;i<=n;i++){
    		sum+=a[i];
    		st.insert(a[i]);
    		if(i>=k){
    			ans=min(ans,sum);
    			auto it=st.rbegin();
    			ans=min(ans,sum-*it+lr[i+1]);
    			ans=min(ans,sum-*it+pr[l-1]);
    			st.erase(st.find(a[l]));
    			sum-=a[l];
    			l++;
    		}
    		
    	}
    	cout<<ans<<"\n";
    	
    	
    	
    	
    
    
}

    
    return 0;
 
}