minOnSegment

/**
 * Рассмотрим последовательность целых чисел длины N.
 * По ней с шагом 1 двигается “окно” длины K, то есть сначала в “окне” видно первые K чисел,
 * на следующем шаге в “окне” уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности.
 * Требуется для каждого положения “окна” определить минимум в нём.
 *
Входные данные
В первой строке входных данных содержатся два числа N и K (1 ≤  N ≤  150000, 1 ≤ K ≤ 10000, K ≤  N)
 – длины последовательности и “окна”, соответственно. На следующей строке находятся N чисел – сама последовательность.

Выходные данные
Выходые данные должны содержать N − K + 1 строк – минимумы для каждого положения “окна”.
 */
#include <stdexcept>
#include <iostream>
#include <vector>

using namespace std;

class Node {
public:
    Node* pnext, *pprev;
    int data;

    Node(int x = 0): data(x), pnext(nullptr), pprev(nullptr) {}
    Node(int x, Node* next, Node* prev = nullptr): data(x), pnext(next), pprev(prev) {}
};

class DequeAsLinkedList {
private:
    Node* head;
    Node* tail;
public:
    DequeAsLinkedList(): head(new Node()), tail(new Node()) {
        head->pnext = tail;
        tail->pprev = head;
    }

    void push_front(int elem) {
        auto newNode = new Node(elem, head->pnext, head);
        head->pnext->pprev = newNode;
        head->pnext = newNode;
    }

    int pop_front() {
        if (head->pnext == tail)
            throw out_of_range("Deque is empty!");
        int res = head->pnext->data;
        auto oldNode = head->pnext;
        head->pnext = oldNode->pnext;
        head->pnext->pprev = head;
        delete oldNode;
        return res;
    }

    void push_back(int elem) {
        auto newNode = new Node(elem, tail, tail->pprev);
        tail->pprev->pnext = newNode;
        tail->pprev = newNode;
    }

    int pop_back() {
        if (head->pnext == tail)
            throw out_of_range("Deque is empty!");
        auto oldNode = tail->pprev;
        int res = oldNode->data;
        tail->pprev = oldNode->pprev;
        tail->pprev->pnext = tail;
        delete oldNode;
        return res;
    }

    bool empty() {
        return head->pnext == tail;
    }

    int back() {
        if (this->empty())
            throw out_of_range("Stack is empty");
        return tail->pprev->data;
    }

    int front() {
        if (this->empty())
            throw out_of_range("Stack is empty");
        return head->pnext->data;
    }

    void pr() {
        if (head == tail->pprev) {
            cout << "Stack is empty!" << endl;
            return;
        }

        Node* e = head->pnext;
        while (e != tail) {
            cout << e->data << " ";
            e = e->pnext;
        }
        cout << endl;
    }

    ~DequeAsLinkedList() {
        auto e = head;
        auto d = head;
        while (d != tail) {
            d = e;
            e = e->pnext;
            delete d;
        }
    }
};

class QueueWithMin {
    DequeAsLinkedList deque;
public:
    QueueWithMin(): deque() {}

    void push(int elem) {
        while (!deque.empty() && deque.back() > elem) {
            deque.pop_back();
        }
        deque.push_back(elem);
    }

    void pop(int removed_elem) {
        if (deque.front() == removed_elem)
            deque.pop_front();
    }

    int min() {
        return deque.front();
    }

    bool empty() {
        return deque.empty();
    }

    void pr() {
        deque.pr();
    }
};

int main() {
   int n, k;
   cin >> n >> k;
   vector<int> nums(n);
   for (int i = 0; i < n; i++) {
       cin >> nums[i];
   }
   QueueWithMin s;

   for (int i = 0; i < k; i++) {
       s.push(nums[i]);
   }

   for (int i = 0; i < n - k + 1; i++) {
       cout << s.min() << endl;
       s.pop(nums[i]);
       if (i + k < n)
           s.push(nums[i+k]);
   }
}