> #include<cstdio>
> int f[1000005],p[1000005],q[1000005],ans1[1000005],ans2[1000005],p1,p2,q1,q2,n,m,i;
> int main()
> {
>     scanf("%d%d",&n,&m);
>     for (i=0;i<n;i++) scanf("%d",&f[i]);
>     p1=0;p2=0;q1=0;q2=0;
>     for (i=0;i<n;i++)
>     {
> 		while (f[i]<=f[p[p2-1]]&&p2>p1) p2--;
> 		if (p2==p1) p[p2++]=i;else p[p2++]=i;
> 		while (f[i]>=f[q[q2-1]]&&q2>q1) q2--;
> 		if (q2==q1) q[q2++]=i;else q[q2++]=i;
> 		if (i-p[p1]>=m) p1++;
> 		if (i-q[q1]>=m) q1++;
> 		if (i>=m-1) {ans1[i]=f[p[p1]];ans2[i]=f[q[q1]];}
> 	}
> 	printf("%d",ans1[m-1]);for (i=m;i<n;i++) printf(" %d",ans1[i]);printf("\n");
> 	printf("%d",ans2[m-1]);for (i=m;i<n;i++) printf(" %d",ans2[i]);printf("\n");
> }