#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n,q[N],a[N],m,tail=-1,head=0;
/*
1.判断队列是否为空 tail>=head 队列不为空
2.q[++tail] = x
3.队首出队head++;
4.tail--
*/
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	//i和q[head]距离<=m
	for(int i=1;i<=n;i++){
		while(tail>=head && a[i]<=a[q[tail]])--tail;
		q[++tail] = i;
		while(tail>=head && i-q[head]+1>m)head++;
		if(i>=m)cout<<a[q[head]]<<" ";
	}
	cout<<endl;
	tail=-1,head=0;
	for(int i=1;i<=n;i++){
		while(tail>=head && a[i]>=a[q[tail]])--tail;
		q[++tail] = i;
		while(tail>=head && i-q[head]+1>m)head++;
		if(i>=m)cout<<a[q[head]]<<" ";
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
int n,m,a[N],sum[N],f[N];
int q[N],tail=-1,head=0;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i] = sum[i-1]+a[i];
	}
	int res = -1e18;
	for(int i=1;i<=n;i++){
		//1.队尾入队，sum[i-1]<=sum[q[tail]
		while(tail>=head && sum[i-1]<=sum[q[tail]])--tail;
		q[++tail] = i-1;
		//2.队首出队 q[head]<i-m
		while(tail>=head && q[head]<i-m)++head;
		int j = q[head];
		f[i] = sum[i]-sum[j];
		res = max(res,f[i]);
	}
	cout<<res<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,a[N],f[N],m;
int q[N],tail=-1,head=0;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		while(tail>=head && f[i-1]<=f[q[tail]])tail--;
		q[++tail] = i-1;
		while(tail>=head && q[head]<i-m)head++;
		int j = q[head];
		f[i] = f[j]+a[i];
	}
	int res = 1e9;
	for(int i=n-m+1;i<=n;i++){
		res = min(res,f[i]);
	}
	cout<<res<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n,a[N],sum[N],f[N],m;
int tail=-1,head=0,q[N];
signed main(){
	cin>>n>>m;n++;
	for(int i=2;i<=n;i++){
		cin>>a[i];
		sum[i] = sum[i-1]+a[i];
	}
	int res = 0;
	q[++tail] = 1;
	for(int i=2;i<=n;i++){
		while(tail>=head && f[i-1]-sum[i]>=f[q[tail]-1]-sum[q[tail]])tail--;
		q[++tail] = i;
		while(tail>=head && q[head]<i-m)head++;
		int j = q[head];
		f[i] = sum[i]+f[j-1]-sum[j];
	//	cout<<i<<" "<<f[i]<<endl;
	}
	cout<<f[n]<<endl;
	return 0;
}