int Solve(vector<int> arr, int d)
{
    int mn, mx;
    deque<int> mmi;
    mmi.push_back(0);
    for(int i = 1; i < d; mmi.push_back(i), i++)
        while(!mmi.empty() && arr[mmi.back()] < arr[i])
            mmi.pop_back();
    mn = mx = mmi.front();
    for(int i = d; i < arr.size(); i++)
    {
        if(mx == i - d)
            mmi.pop_front();
        while(!mmi.empty() && arr[mmi.back()] <= arr[i])
            mmi.pop_back();
        mmi.push_back(i);
        mx = mmi.front();
        mn = arr[mx] < arr[mn] ? mx : mn;
    }

    return arr[mn];
}

vector<int> solve(vector<int> arr, vector<int> queries) {
    vector<int> res;
    int N = arr.size();
    for (int i = 0; i < queries.size(); i++) {
        int d = queries[i];
        vector<int> q;
        int mini = INT32_MAX; 
        for (int j = 0; j < N;j ++){ 
            // q is a decreasing vector
            while (!q.empty() && q.back() < arr[j]) {
                q.pop_back();
            }
            q.push_back(arr[j]);
            if (j + 1 >= d) {
                if (mini > q[0]) {
                    mini = q[0];
                }
                if (q[0] == arr[j+1-d]) {
                    q.erase(q.begin());
                }
            }
        } 
        res.push_back(mini);
    }
    
    return res;
}

from collections import deque
def solve1(arr,dis):
    ans=[];d=deque();i=0;j=0
    while j<len(arr):
        while d and d[-1]<arr[j]:
            d.pop()
        d.append(arr[j])
        if j-i+1<dis:
            j+=1
        else:
            ans.append(d[0])
            if d[0]==arr[i]:
                d.popleft()
            i+=1
            j+=1
    return min(ans)
    

def solve(arr, queries):
    res=[]
    for i in queries:
        if i==1:
            res.append(min(arr))
        elif i==len(arr):
            res.append(max(arr))
        else:
            res.append(solve1(arr,i))
    return res

def solve(arr, queries):
  n = len(arr)
  minimums = []
  for d in queries:
    maximum = minimum = max(arr[0:d])
    for i in range(1, n - d + 1):
      # New upper bound is higher
      if arr[i + d - 1] > maximum:
        maximum = arr[i + d - 1]
      # Previous lower bound was the maximum
      elif arr[i - 1] == maximum:
        maximum = max(arr[i : i + d])
      # Else, we mantain the current maximum
      
      # We update the minimum
      if maximum < minimum:
        minimum = maximum
    minimums.append(minimum)
  return minimums

vector<int> solve(vector<int> arr, vector<int> queries) {
    vector<int> result;
    for(int i=0;i<queries.size();i++)
    {
        int k=queries[i];
        vector<int> v;
        deque<int> dq;
        for(int i=0;i<k;i++)
        {
            while(dq.empty()!=true && arr[i]>arr[dq.back()])
                dq.pop_back();
            dq.push_back(i);
        }
        for(int i=k;i<arr.size();i++)
        {
            v.push_back(arr[dq.front()]);
            while(dq.empty()!=true && dq.front()<=i-k)
                dq.pop_front();
            while(dq.empty()!=true && arr[i]>=arr[dq.back()])
                dq.pop_back();
            dq.push_back(i);
        }
        v.push_back(arr[dq.front()]);   
        sort(v.begin(),v.end());
        result.push_back(v[0]);
    }
    return result;
}