#include<iostream>
#define MAXN 1000010
using namespace std;
int q[MAXN],idq[MAXN],idp[MAXN],p[MAXN];//分别是min队列、max队列及其中元素的序号
int ans[MAXN],ql=0,qr=-1,pl=0,pr=-1,n=0,k=0;//ql、qr是q队列的左端点、右端点，p队列同理
int main()
{
  int i=1,a=0;
  ios::sync_with_stdio(0);
  cin>>n>>k;
  for(i=1;i<=n;i++)
  {
    cin>>a;
    for(;qr>=ql && q[qr]>=a;qr--);
    q[++qr]=a;
    idq[qr]=i;
    if(idq[ql]+k==i)
    {
      ql++;
    }
    for(;pr>=pl && p[pr]<=a;pr--);
    p[++pr]=a;
    idp[pr]=i;
    if(idp[pl]+k==i)
    {
      pl++;
    }
    if(i<k)
    {
      continue;
    }
    cout<<q[ql]<<' ';
    ans[i]=p[pl];//max与min同时计算，留到最后输出
  }
  cout<<endl;
  for(i=k;i<=n;i++)
  {
    cout<<ans[i]<<' ';
  }
  cout<<endl;
  return 0;
}

大佬们请不要嫌弃蒟蒻的码风，帮忙看看怎么优化吧、、原则上不打算开O(2)，毕竟NOIP不允许。