带注释（超详细）

//算法思想：维护一个单调队列来模拟滑动窗口。剔除一些没有用的数字。求最大值和求最小值分为两种情况。
//1.求最大值时，每次加入队尾的数字一定要比队列中前一个数字大才能加入队列。
//2.求最小值时，每次加入队尾的数字一定要比队列中钱一个数字小才能加入队列。

//如果当前的队尾元素的值比正在遍历到的a[i]的值大，则把当前的队尾元素删除
//（因为a[i]是新来的，而且a[i]的生命周期比当前的队尾元素的生命周期长且a[i]更小，所以
//删除队尾元素，再和前一个队尾元素作比较，重复操作。

//但是不管当前的数有没有用，都要加入队列。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N=1000010;

int a[N],q[N];
//a[N]表示输入的数组，q[N]表示队列，用来存储输入的数组a[N]的下标

int main(){

    int tt=-1,hh=0; //tt表示队尾，hh表示1队头。
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);

    for(int i=0;i<n;i++){
    //遍历数组a[N]

        if((hh<=tt)&&(i-k+1)>q[hh]) hh++;
        //确保当前的队列在滑动窗口内部。
        while( hh<=tt && a[q[tt]]>=a[i]) tt--;
        //如果当前的队尾元素的值比正在遍历到的a[i]的值大，则把当前的队尾元素删除
        //（因为a[i]是新来的，而且a[i]的生命周期比当前的队尾元素的生命周期长且
        //a[i]更小，所以删除队尾元素，再和前一个队尾元素作比较，重复操作。
        q[++tt]=i;

        if(i-k>=-1)  printf("%d ",a[q[hh]]); //当队列中够三个数字才能输出答案。
        //为什么要输出队头数字呢？
        //因为如果加入的数字比当前队尾的数字大，也是要加入的。如果加入的数字比队列中所有的元素都小，是
        //要依次替换队列中的元素的。

    }
    cout<<endl;

    tt=-1,hh=0; 

    for(int i=0;i<n;i++){

        if((hh<=tt)&&(i-k+1)>q[hh]) hh++;

        while( hh<=tt && a[q[tt]]<=a[i]) tt--;//求最大与最小相反
        q[++tt]=i;

        if(i-k>=-1)  printf("%d ",a[q[hh]]); 

    }
    return 0;
}