本题是一个滑动窗口问题，在移动过程中改变的是第一个数被丢掉和下一个数加进来。那么可以建立一个队列，如果当前进来的这个数比前面的某些数要大的话就需要出队，因为由于这个更大的数的存在前面的数就不可能变成最大的数。那么就需要直接从队列里面删除。如果第一个在窗口移动的时候被丢掉了同样也要删除。如果新加进来的比队列里面的数要小，那么他就还有称为最大值的潜力，将他放在队尾保留。求最小值同样也是这样。
要注意：由于在窗口移动过程中丢掉的不能直接使用数值是否相等来判断，因为可能有一样的数字造成错误的删除。保存下标才是明智之举。 
#include <bits/stdc++.h>


using namespace std;
const int maxn = 1e6+10;
int a[maxn];
int n, k;
deque<int> max_dq;
deque<int> min_dq;

void print_min() {
    for (int i=1;i<=n;i++) {
        //如果当前的数比队列里面第一个要大，那么直接将队列全部弹出
        while (!max_dq.empty() && a[i]>=a[max_dq.back()]) {
            max_dq.pop_back();
        }
        max_dq.push_back(i);
        if (!max_dq.empty() && i-max_dq.front()+1>k) {
            max_dq.pop_front();
        }
        if (i>=k)
        printf("%d ", a[max_dq.front()]);
    }
}

void print_max() {
    for (int i=1;i<=n;i++) {
        //如果当前的数比队列里面第一个要大，那么直接将队列全部弹出
        while (!min_dq.empty() && a[i]<=a[min_dq.back()]) {
            min_dq.pop_back();
        }
        min_dq.push_back(i);
        if (!min_dq.empty() && i-min_dq.front()+1>k) {
            min_dq.pop_front();
        }
        if (i>=k)
        printf("%d ", a[min_dq.front()]);
    }
}

int main() {
    cin>>n>>k;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    print_max();
    cout<<endl;
    print_min();
    return 0;
}