Monotonic Queue

/*
Monotinic Queue

Nalazi min/max za svaki interval duzine len u O(N)
*/

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

const int N=1e5+10;

int a[N], sol[N];
int n, len;

void monotonicQueue (const int &len, const int &n)
{
    deque<pair<int, int> > dq;
    for (int i=1;i<=n;i++)
    {
        int x=a[i];
        while (dq.size()>0 && dq.back().first>=x) dq.pop_back();
        while (dq.size()>0 && dq.front().second<i-len+1) dq.pop_front();
        dq.emplace_back(x, i);
        if (i-len+1>0) sol[i-len+1]=dq.front().first;
    }
}

int main()
{
    cin >> n >> len;
    for (int i=1;i<=n;i++) cin >> a[i];

    monotonicQueue(len, n);

    for (int i=1;i<=n-len+1;i++) cout << sol[i] << " ";

    return 0;
}