#include <bits/stdc++.h>
#include <gtest/gtest.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

// For each of the contiguous subarrays of size K of each array, you
// have to print the maximum integer.
// Example: K=2 array {3,4,6,3,4}
//    subarrays: {3,4}, {4,6}, {6,3}, {3,4}
//    max of subarrays: {4,6,6,4}

// Optimized Approach Using Deque (Double-Ended Queue)
// Time Complexity: O(n)
// Space Complexity: O(k)
//
// Uses a deque to store indices of array elements such that:
//
// The front of the deque always holds the index of the maximum
// element in the current window.

// Elements smaller than the current element are removed from the
// rear, as they can never be the maximum.

// Indices outside the current window are removed from the front. This
// ensures that each element is added and removed at most once,
// leading to linear time complexity.

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> resultIndices;

    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: push_back i=" << i << " "; for (auto i: deque) {cerr << i << "(" << arr[i] << ") ";} cerr << endl;
    }

    cout << "  firstwindow deque: {";
    for (auto i: deque) cout << i << ",";
    cout << "}" << 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++)
    {
        resultIndices.push_back(deque.front());
        
        cerr << "i: " << i << " window: " << i - K + 1 << " to " << i << endl;
        cout << "  resultIndices.push_back: " << deque.front() << endl;
        cout << "  resultIndices: "; for (auto i: resultIndices) cout << i << " "; cout << 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]: "<< 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;
        cout << "  deque: {";
        for (auto i: deque) cout << i << ",";
        cout << "}" << endl;
    }

    resultIndices.push_back(deque.front());
    cout << "Done" << endl;
    cout << "Input: "; for (auto i: arr) cout << i << " "; cout << endl;
    cout << "  resultIndices: "; for (auto i: resultIndices) cout << i << " "; cout << endl;

    return resultIndices
        ;
}

int main()
{
    //   K, input,                 expected
    vector<tuple<int, vector<int>, vector<int>>> testCases = {
        //{3, {1,2,3,4,5,6,7,8},       {3,4,5,6,7,8}},
        //{3, {9,8,7,6,5,4},           {9,8,7,6}},        
        //{2, {3,4,6,3,4},           {4,6,6,4}},        
        {3, {12,1,78,90,57,89,56}, {78,90,90,90,89}},
        //{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);
        cout << "input: "; for (auto i: input) {cout << i << " ";} cout << endl;
        vector<int> resultIdx = getKMax(input, input.size(), K);
        vector<int> result; for (auto i: resultIdx) result.push_back(input.at(i));
        cout << "  result: ";
        for (auto i: result) {cout << i << " ";} cout << endl;
        cout << "expected: ";
        for (auto i: expected) {cout << i << " ";} cout << endl;
        cout << "----------------\n";

        EXPECT_EQ(result, expected);
    }
    return 0;
}

/*
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;
}
*/