#include<bits/stdc++.h>
using namespace std;
deque<int> mi,ma,imi,ima;
int n,k,a[1050000],i;
int main() {
	cin>>n>>k;
	for(i=1;i<=n;i++){
		cin>>a[i];
	}
	//处理min
	for(i=1;i<k;i++){
		while(!mi.empty()&&mi.back()>=a[i]){
			mi.pop_front();
			imi.pop_front();
		}
		mi.push_back(a[i]);
		imi.push_back(i);
	}
	
	for(i=k;i<=n;i++){
		//过期出队
		while(!imi.empty()&&i-imi.front()>=k){
			imi.pop_front();
			mi.pop_front();
		}
		//入队前清
		//若x进入后，x<队列尾，pop
		while(!mi.empty()&&a[i]<mi.back()){
			imi.pop_back();
			mi.pop_back();
		}
		mi.push_back(a[i]);
		imi.push_back(i);
        cout<<mi.front()<<" ";
	}
	
	cout<<endl;
	
	//处理max
	for(i=1;i<k;i++){
		while(!ma.empty()&&ma.back()<=a[i]){
			ma.pop_front();
			ima.pop_front();
		}
		ma.push_back(a[i]);
		ima.push_back(i);
	}
	
	for(i=k;i<=n;i++){
		//过期出队
		while(!ima.empty()&&i-ima.front()>=k){
			ima.pop_front();
			ma.pop_front();
		}
		//入队前清
		//若x进入后，队尾<x，pop
		while(!ma.empty()&&ma.back()<a[i]){
			ma.pop_back();
			ima.pop_back();
		}
		ma.push_back(a[i]);
		ima.push_back(i);
		cout<<ma.front()<<" ";
	}
	return 0;
}

记录