代码如下：

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <deque>
using namespace std;
struct node{
    long long x,id;
};
node a[1000005];
deque <node> q1,q2;
int n,k;
int main()
{
    cin >> n >> k;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i].x;
        a[i].id = i;
    }
    for(int i = 1 ; i <= k ; ++i){
        if(q1.empty()){
            q1.push_back(a[i]);
        }
        else{
            while(!q1.empty() && q1.back().x > a[i].x){
                q1.pop_back();
            }
            q1.push_back(a[i]);
        }
    }
    cout << q1.front().x << " ";
    for(int i = k + 1,j = 2 ; i <= n ; ++i,++j){
        while(q1.front().id < j){
            q1.pop_front();    
        }
        if(q1.empty()){
            q1.push_back(a[i]);
        }
        else{
            while(!q1.empty() && q1.back().x > a[i].x){
                q1.pop_back();
            }
            q1.push_back(a[i]);
        }
        cout << q1.front().x << " ";
    }
    cout << endl;
    for(int i = 1 ; i <= k ; ++i){
        if(q2.empty()){
            q2.push_back(a[i]);
        }
        else{
            while(!q2.empty() && q2.back().x < a[i].x){
                q2.pop_back();
            }
            q2.push_back(a[i]);
        }
    }
    cout << q2.front().x << " ";
    for(int i = k + 1,j = 2 ; i <= n ; ++i,++j){
        while(q2.front().id < j){
            q2.pop_front();    
        }
        if(q2.empty()){
            q2.push_back(a[i]);
        }
        else{
            while(!q2.empty() && q2.back().x < a[i].x){
                q2.pop_back();
            }
            q2.push_back(a[i]);
        }
        cout << q2.front().x << " ";
    }
    return 0;
}