qtbg

#include<bits/stdc++.h>
using namespace std;
deque<int> x;//x最大y最小
deque<int> y;
int main() {
    freopen("window.in","r",stdin);
    freopen("window.out","w",stdout);
    int s[1000010];
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
    }
    for(int i=1;i<=n;i++){
        while(!y.empty()&&s[y.back()]>=s[i]){
            y.pop_back();
        }
        y.push_back(i);
        while(!y.empty()&&y.front()<=i-k){
            y.pop_front();
        }
        if(i>=k){
            printf("%d ",s[y.front()]);
        }
    }
    cout<<endl;
    for(int i=1;i<=n;i++){
        while(!x.empty()&&s[x.back()]<=s[i]){
            x.pop_back();
        }
        x.push_back(i);
        while(!x.empty()&&x.front()<=i-k){
            x.pop_front();
        }
        if(i>=k){
            printf("%d ",s[x.front()]);
        }
    }
    return 0;
}