SPOJ - ARRAYSUB

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    int k; cin >> k;
    deque<int> candidates;
    for (int i = 0; i < n; ++i) {
        while (!candidates.empty() && a[candidates.back()] <= a[i]) candidates.pop_back();
        candidates.push_back(i);
        if (!candidates.empty() && candidates.front()+k == i) candidates.pop_front();
        if (i >= k-1) cout << a[candidates.front()] << ' ';
    }
    cout << endl;
    return 0;
}