首先我们考虑暴力做法。
O(n^2)，枚举所有长度为k的区间，然后取区间最大值。
然后考虑一下优化，就是我们能不能枚举一遍就能求出答案，也就是取区间最大值能否在O(1)的时间内求出来呢？是可以的。我们需要一个队列来维护，为了每次直接O(1)求出最大值，我们需要构造一个单调递减的序列，这样每次取序列的第一个元素就是最大值。那么考虑一下当一个元素在和单调递减序列中间元素相同时，我们需要怎么做？为了使得这个序列是递减的我们需要将后面的元素全部丢弃，因为它对答案已经没有贡献，然后再把这个元素放到后面，使其继续保持递减性质。从上面的操作看我们需要一个可以在尾部进行插入与删除，在头部进行删除的容器(最大值不在区间内，需要将其移除)，那么这个容器就是双端队列。
然后就出来了。递减只需要构造递增序列即可。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 20;
typedef long long int ll;
ll a[maxn];
void solved(){
    ll n,k;cin>>n>>k;
    for(int i = 1; i <= n; i++)cin>>a[i];
    deque<ll>m;
    for(int i = 1; i <= n; i++){
        while(!m.empty() && i - k  >= m.front())m.pop_front();// 考虑最大值是否越界(队头出队) 
        while(!m.empty() && a[i] <= a[m.back()])m.pop_back(); //是否满足单调性(队尾出队)
        m.push_back(i);
        if(i >= k){
            cout<<a[m.front()]<<" "; 
        } 
    } 
    cout<<endl;
    deque<ll>M;
    for(int i = 1; i <= n; i++){
        while(!M.empty() && i - k  >= M.front())M.pop_front();// 考虑最大值是否越界(队头出队) 
        while(!M.empty() && a[i] >= a[M.back()])M.pop_back(); //是否满足单调性(队尾出队)
        M.push_back(i);
        if(i >= k){
            cout<<a[M.front()]<<" "; 
        } 
    }
}
int main(){
    solved();
    return 0;
}