Минимум на отрезке (границы меняются)

[Skyfall]

Задача
   Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается “окно” длины K, то есть сначала в “окне” видно первые K чисел, на следующем шаге в “окне” уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения “окна” определить минимум в нём.
Входные данные
   Впервой строке входных данных содержатся два числа N и K ($1 \leqslant N \leqslant 150\, 000, 1 \leqslant K \leqslant 10\, 000, K \leqslant N$) – длины последовательности и “окна”, соответственно. На следующей строке находятся N чисел – сама последовательность.
Выходные данные
   Выходные данные должны содержать $ N - K + 1 $ строк – минимумы для каждого положения “окна”.

Ограничение по времени, сек: 1
Ограничение по памяти, мегабайт: 64

Проблема
Мой код "не влазит" в ограничение по времени (1,8 сек). Подскажите, пожалуйста, как улучшить алгоритм. Мой алгоритм прост: пройти по последовательности с окном, каждый раз находя в окне min.

Используется синтаксис C++

#include <iostream>
using namespace std;

int main()
{
        int N, K, min = 2147483647;
        cin >> N >> K;
        int *arr = new int[N];

        for (int i = 0; i<N; ++i)
                cin >> arr[i];

        for (int i = 0; i < N-K+1; ++i)
        {
                min = 2147483647;
                for (int j = i; j < i+K ; ++j)
                {
                        if (min>arr[j])
                                min = arr[j];
                }
                cout << min << endl;
        }

        return 0;
}
 

[Pavia]

Skyfall
А что у вас идей нет? Я как минимум знаю 2 идеи которые могут ускорить код.
1) Можно к примеру рассмотреть какое число добавилось и какое ушло. И на основе этого уже либо запускать поиск минимума в окне или не запускать.
2) Или второй вариант вычислить минимум в 2,4,8 и тд. Памяти много хватит. И тогда поиск в окне минимума будет не O(N), а O(Log(K)).