【题意】
移动区间(长度固定)最值问题。
【分析】 这类思想在单调队列优化思想中尤其重要：区间长度为k，求区间内的最大值，考虑第i个数和第j个数，j-i<k，若a[i]<a[j]，那么a[i]将毫无用处。直觉上理解，因为窗口的移动，a[i]要比a[j]先移出去，无论如何，区间的最大值都不可能是a[i]。 这样，考虑构造一个单调递增的队列，存放相应的序号，当a[队尾]>=要入队数据a[i]，删除队尾元素；当队头<=i-k时，删除队头元素。
/**
单调队列：
加入找最小数，考虑顺序a,b(b在a的后面)，若b<a,当b入队列后，a不可能称为最小值(a比b先出)，删去。
每个元素出队列和入队列一次，时间复杂度为O(n)
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
const int nn=1100000;
int n,k;
int a[nn];
int queue[nn];
int head,tail;
void Min()
{
int i;
int head=1;
int tail=0;
for(i=0;i<k-1;i++)
{
while(tail>=head&&a[i]<=a[queue[tail]])tail--;
++tail;
queue[tail]=i;
}
for(i=k-1;i<n;i++)
{
while(head<=tail&&a[i]<=a[queue[tail]])tail--;
tail++;
queue[tail]=i;
while(queue[head]<i-k+1)head++; //注意这是队头不在范围内时，将队头前移。
cout<<a[queue[head]];
if(i==n-1)cout<<endl;
else cout<<' ';
}
}
void Max()
{
int i;
int head=1,tail=0;
for(i=0;i<k-1;i++)
{
while(head<=tail&&a[queue[tail]]<=a[i])tail--;
tail++;
queue[tail]=i;
}
for(i=k-1;i<n;i++)
{
while(head<=tail&&a[queue[tail]]<=a[i])tail--;
tail++;
queue[tail]=i;
if(queue[head]<i-k+1)head++;
cout<<a[queue[head]];
if(i==n-1)cout<<endl;
else cout<<' ';
}
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)cin>>a[i];
Min();
Max();
return 0;
}