[//]: # 滑动窗口详细注释版
#include<iostream>
using namespace std;
const int N = 1000010;
int n,k;
int a[N],q[N];//q[N]用于储存数组的下标
int main(){
scanf("%d %d",&n,&k);
for(int i = 0;i < n;i++){
scanf("%d", &a[i]);
}
//使hh<=tt是为了使得队列不为空,如果 hh 小于 tt,说明队列中至少有一个元素;如果 hh 等于 tt,说明队列中只有一个元素;而如果 hh 大于 tt,说明队列为空。
int hh = 0,tt = -1;
for(int i = 0;i < n;i++){
//维持滑动窗口大小:当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的滑动窗口大小,
//则队列弹出头元素以维持队列的大小
if(hh <= tt && k < i - q[hh] + 1) hh++;
//队列窗口大小的计算通过末尾下标减去前面下标+1实现
//比较当前元素和队尾元素的大小,若队尾元素比当前元素大则删除,确保队列的单调增性
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
//在队尾加入新元素
q[++tt] = i;
//当窗口中开始有k个数的时候开始输出最小值
if(i + 1 >= k) printf("%d ",a[q[hh]]);
}
puts("");
hh = 0,tt = -1;
for(int i = 0;i < n;i++){
//维持滑动窗口大小:当队列不为空(hh <= tt) 且 当当前滑动窗口的大小(i - q[hh] + 1)>我们设定的滑动窗口大小,
//则队列弹出头元素以维持队列的大小
if(hh <= tt && k < i - q[hh] + 1) hh++;
//比较当前元素和队尾元素的大小,若队尾元素比当前元素小则删除,确保队列的单调减性,两边是对称的
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
//在队尾加入新元素
q[++tt] = i;
//当窗口中开始有k个数的时候开始输出最小值
if(i + 1 >= k) printf("%d ",a[q[hh]]);
}
return 0;
}