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

//**********************************
// HackerRank Prepare C++: Deque-STL
//**********************************

// GeeksForGeeks:
// A stl deque based method for printing maximum element of all
// subarrays of size K

void printKMax(int arr[], int n, int k)
{
    std::deque<int> deque;
    vector<int> result;

    for (int i = 0; i < k; i++)
    {
        // If element at back is smaller than current elem remove from
        // deque. Continue until all deque elements are greater than
        // current element. Then push_back element.
        while (!deque.empty() && arr[deque.back()] < arr[i])
            deque.pop_back();
        deque.push_back(i);
    }
    
    for (int i = k; i < n; i++)
    {
        result.push_back(deque.front());
        
        // remove elements not in current window i-k+1 to i
        while (!deque.empty() && deque.front() < i - k + 1)
            deque.pop_front();

        // Remove back elements as in processing first window
        while (!deque.empty() && arr[deque.back()] < arr[i])
            deque.pop_back();
        deque.push_back(i);
    }

    result.push_back(deque.front());
    
    for (auto i: result) cout << arr[i] << " ";
    cout << endl;
}


vector<int> getKMax(const vector<int>& arr, int N, int K)
{
    // Order deque from max to min of arr index of elements
    std::deque<int> deque;
    vector<int> result;

    cerr << "window size K: " << K << endl;
    
    // Process first window:
    // 1. Run a loop to insert fist K elements in deque. If element at
    // back is smaller than current elem remove from deque. Continue
    // until all deque elements are greater than current element. Then
    // push_back element.
    cerr << " firstwindow: 0 to " << K - 1 << endl;    
    for (int i = 0; i < K; i++)
    {
        while (!deque.empty() && arr[deque.back()] < arr[i])
        {
            cerr << "  i: " << i << " deque back " << deque.back() << "(" << arr[deque.back()] << ") less than elem " << i << "(" << arr[i] << ") --> pop back" << endl;
            deque.pop_back();
        }        
        deque.push_back(i);
        cerr << "deque: i=" << i << " "; for (auto i: deque) {cerr << i << "(" << arr[i] << ") ";} cerr << endl;
    }
    
    // 2. Process remaining elements - run loop from K to end of arr.
    //      - insert deque front in result vector;.
    //      - pop front elements if element not in current window
    //      - insert next element using step 1 paradigm

    // process subsequent windows
    for (int i = K; i < N; i++)
    {
        result.push_back(deque.front());
        
        cerr << "i: " << i << " window: " << i - K + 1 << " to " << i << endl;

        // remove elements not in current window i-K+1 to i
        while (!deque.empty() && deque.front() < i - K + 1)
        {
            int e = deque.front();
            cerr << "  index " << e << " not in window, pop front --> " << e << "(" << arr[e] << ")" << endl;
            deque.pop_front();
        }

       // As in processing first window, if element at back is smaller
       // than current elem remove from deque. Continue until all
       // deque elements are greater than current element. Then
       // push_back element.
        while (!deque.empty() && arr[deque.back()] < arr[i])
        {
            cerr << "  i: " << i << " deque back " << deque.back() << "(" << arr[deque.back()] << ") less than elem " << i << "(" << arr[i] << ") --> pop back" << endl;
            deque.pop_back();
        }        
        deque.push_back(i);
        cerr << "  deque: i=" << i << " "; for (auto i: deque) {cerr << i << "(" << arr[i] << ") ";} cerr << endl;
    }

    result.push_back(deque.front());

    for (auto i: result) {cout << i << " ";} cout << endl;
    return result;
}
 
int main()
{
    //             K, input      , expected
    vector<tuple<int, vector<int>, vector<int>>> testCases = {
        {3,{12,1,78,90,57,89,56}, {78,90,90,90,89}},
        {2,{3,4,6,3,4}, {4,6,6,4}},
        {4,{3,4,5,8,1,4,10}, {8,8,8,10}},
    };

    for (auto test: testCases)
    {
        int K = get<0>(test);
        const vector<int>& input = get<1>(test);
        const vector<int>& expected = get<2>(test);
        for (auto i: input) {cout << i << " ";} cout << endl;
        vector<int> result = getKMax(input, input.size(), K);
        for (auto i: result) {cout << input.at(i) << " ";} cout << endl;
        for (auto i: expected) {cout << i << " ";} cout << endl;
        cout << "----------------\n";
    }
    return 0;
}