zirrtu @ 2017-01-22 11:16:07
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 1010000+5
#define INF 2147483647
using namespace std;
int a[MAXN],q[MAXN],p[MAXN],cnt,l=0,r=1,CNT,cnt2,CNT2,l2=0,r2=1,p2[MAXN],q2[MAXN],n,k;
void add(int x)
{
q[++r]=x;p[r]=++cnt;
while(l<r&&q[r-1]>=q[r])
{
r--;
q[r]=x;
p[r]=cnt;
}
}
void add2(int x)
{
q2[++r2]=x;p2[r2]=++cnt2;
while(l2<r2&&q2[r2-1]<=q2[r2])
{
r2--;
q2[r2]=x;
p2[r2]=cnt2;
}
}
void del()
{
CNT++;
if(p[l]==CNT)l++;
}
void del2()
{
CNT2++;
if(p2[l2]==CNT2)l2++;
}
int qu()
{
return q[l];
}
int qu2()
{return q2[l2];}
int main()
{
int i,j,k,aa;
for(i=1;i<=MAXN;i++)q[i]=INF;
for(i=1;i<=MAXN;i++)q2[i]=-INF;
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=k;i++)
add(a[i]);cout<<qu()<<" ";
for(i=k+1;i<=n;i++)
{
add(a[i]);
del();
cout<<qu()<<" ";
}
cout<<endl;
for(i=1;i<=k;i++)
add2(a[i]);cout<<qu2()<<" ";
for(i=k+1;i<=n;i++)
{
add2(a[i]);
del2();
cout<<qu2()<<" ";
}
return 0;
}