void add(deque<int>& q, int v){
    while(!q.empty() && q.back() < v) q.pop_back();
    q.push_back(v);      
}

int getMax(deque<int>& q){ return q.front(); }

void pop(deque<int>& q, int rv){
    if(!q.empty() && rv == q.front()) q.pop_front();
}

int computeMinOfSubarrays(vector<int> maxs){
    int ans = INT_MAX;
    for(auto m : maxs) ans = min(ans, m);
    return ans;    
}

vector<int> solve(vector<int> arr, vector<int> queries) {
   vector<int> mins;
   for(auto subArrayLength : queries){
       deque<int> q; vector<int> maxs; 
       int size = 0;
       int toBeRemoved = 0;
       for(int i=0; i<arr.size(); ++i){
           add(q, arr[i]);
           size++;
           if(size == subArrayLength){
               size -= 1;
               maxs.push_back(getMax(q));
               pop(q, arr[toBeRemoved++]);
           }
       }
       mins.push_back(computeMinOfSubarrays(maxs));
   } 
   return mins; 
}

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