#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,k;
int a[N];
deque <int> q;
deque <int> p;
signed main(){
    scanf("%d%d",&n,&k);
    int minn=0;
    a[0]=1e9+10;
    q.push_front(0);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++){
        if(a[i]<a[i-1]) q.pop_back();
        q.push_back(i);
        while(q.front()<i-k+1) q.pop_front();
        while(!q.empty()&&a[i]<a[q.front()]) q.pop_front();
       if(i>=k) printf("%d ",a[q.front()]);
    }
    printf("\n");
    for(int i=1;i<=n;i++){
        if(a[i]>a[i-1]) p.pop_back();
        p.push_back(i);
        while(p.front()<i-k+1) p.pop_front();
        while(!p.empty()&&a[i]>a[p.front()]) p.pop_front();
       if(i>=k) printf("%d ",a[p.front()]);
    }
    return 0;
}