C++ :

#include<iostream>
#include<cstdio>
#include<cstring>
#include<deque>
using namespace std;
deque<int> q_max,q_min;
int n,k,a[1000001];
int b[1000001],c[1000001];
void insert(int,bool);
void init();
void work();
int main()
{
	//freopen("window6.in","r",stdin);
	//freopen("window.out","w",stdout);
	init();
	work();
	return 0;
}
void init()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];	
}
void work()
{
	
	for(int i=1;i<k;i++)
	{
		insert(i,0);
		insert(i,1);
	}	
	for(int i=k;i<=n;i++)
	{
		insert(i,0);
		insert(i,1);		
		while(!q_max.empty()&&q_max.front()<i-k+1) q_max.pop_front();
		while(!q_min.empty()&&q_min.front()<i-k+1) q_min.pop_front();
		b[i]=a[q_max.front()];
		c[i]=a[q_min.front()];
	}
	for(int i=k;i<n;i++) cout<<c[i]<<' ';cout<<c[n]<<endl;
	for(int i=k;i<n;i++) cout<<b[i]<<' ';cout<<b[n]<<endl;
}
void insert(int x,bool f)
{	
	if(f)
	{
		while(!q_max.empty() && a[q_max.back()]<=a[x]) q_max.pop_back();
		q_max.push_back(x);
	}
	else
	{
		while(!q_min.empty() && a[q_min.back()]>=a[x]) q_min.pop_back();
		q_min.push_back(x);
	}
}

Pascal :

program ddk;
 var top,tail,n,k,i,j,p,xx,yy:longint;
     q,a,min,max:array[1..1000001]of longint;
  begin
   xx:=1;
   yy:=1;
   readln(n,k);
    for i:=1 to n do
     read(a[i]);
     readln;
      top:=1;tail:=1; q[top]:=1;
      for i:=2 to n do
      begin

       while (top<=tail) and (a[q[tail]]<a[i])
       do  tail:=tail-1;
           inc(tail);

q[tail]:=i;
        while q[tail]-q[top]+1>k do inc(top);
        if i>=k then begin
                     max[xx]:=a[q[top]];
                     xx:=xx+1;
                     end;
         end;
         top:=1;tail:=1; q[top]:=1;
      for i:=2 to n do
      begin

       while (top<=tail) and (a[q[tail]]>a[i])
       do  tail:=tail-1;
           inc(tail);

q[tail]:=i;
        while q[tail]-q[top]+1>k do inc(top);
        if i>=k then begin
                     min[yy]:=a[q[top]];
                     yy:=yy+1;
                     end;
         end;
         for i:=1 to yy-1 do
          begin
          if i<>yy-1 then write(min[i],' ');
           if i=yy-1 then writeln(min[i]);
           end;
         for i:=1 to xx-1 do
          begin
          if i<>xx-1 then write(max[i],' ');
           if i=xx-1 then writeln(max[i]);
           end;
         end.