#include <iostream>
#include <queue>
#include <vector>

using namespace std ;
const int MAXN = 1e6 + 10 ;
int n , k , head = 1 , tail ;
int a[MAXN] , de[MAXN] ;
int main()
{
	cin >> n >> k ;
	for ( int i = 1 ; i <= n ; i ++ )
	{
		cin >> a[i] ;
	}
	for ( int i = 1 ; i <= n ; i ++ )
	{
		while(head<=tail&&de[head] <= i - k ) head ++ ;
		while(head<=tail&&a[de[tail]]>=a[i]) tail -- ; // 如果头部<=尾部且进来的数小于尾部数字 
		de[++tail] = i ;
		if ( i >= k )
		{
			cout << a[de[head]] << " "; 
		} 	
	}
	cout << endl ;
	for ( int i = 1 ; i <= n ; i ++ )
	{
		while(head<=tail&&de[head] <= i - k ) head ++ ;
		while(head<=tail&&a[de[tail]]<=a[i]) tail -- ; // 如果头部<=尾部且进来的数大于尾部数字 
		de[++tail] = i ;
		if ( i >= k )
		{
			cout << a[de[head]] << " "; 
		} 	
	}
	
	return 0 ;
}