1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 const int N=1000010; 5 int maxq[N],minq[N],a[N],ans1[N],ans2[N],lmax,lmin,rmax,rmin; 6 int main(){ 7     int n,k; 8     lmax=lmin=rmax=rmin=0; 9     scanf("%d %d",&n,&k);10     for (int i=1;i<=n;i++)11         scanf("%d",&a[i]);12     for (int i=1;i<=n;i++){13         while (lmax<=rmax&&maxq[lmax]<=i-k) lmax++;14         while (lmin<=rmin&&minq[lmin]<=i-k) lmin++;15         while (rmax>=lmax&&a[maxq[rmax]]<a[i]) rmax--;16         maxq[++rmax]=i;17         while (rmin>=lmin&&a[minq[rmin]]>a[i]) rmin--;18         minq[++rmin]=i;19         ans1[i]=a[minq[lmin]];20         ans2[i]=a[maxq[lmax]];21     }22     for (int i=k;i<=n;i++)23         printf("%d ",ans1[i]);24     printf("\n");25     for (int i=k;i<=n;i++)26         printf("%d ",ans2[i]);27     return 0;28 }