// Struct { array value, index in the array }
    public static class IndexTracker {
        public int value;
        public int index;
        
        public IndexTracker(int value, int index) {
            this.value = value;
            this.index = index;
        }
    }
    
    // Helps sort the list in descending order
    public static class IndexTrackerComparator implements Comparator<IndexTracker> {
        @Override
        public int compare(IndexTracker trackerA, IndexTracker trackerB) {
            return Integer.compare(trackerB.value, trackerA.value);
        }
    }

    public static List<Integer> solve(List<Integer> arr, List<Integer> queries) { 
	// Get reverse sorted list of struct {value: arr[i], index: i} 
        List<IndexTracker> trackers = new ArrayList<>();
        for (int i = 0; i < arr.size(); i++) {
            IndexTracker tracker = new IndexTracker(arr.get(i), i);
            trackers.add(tracker);
        }
        Collections.sort(trackers, new IndexTrackerComparator());
        
        // Loop through each query
        List<Integer> minima = new ArrayList<>();
        for (int query : queries) {
            minima.add(minOfMaxSubarray(trackers, arr.size(), query));
        }
        
        return minima;
    }
    

    public static int minOfMaxSubarray(List<IndexTracker> sortedTrackers, int arraySize, int length) {
        // Create a list of subarray max values
        List<Integer> marks = new ArrayList<>();
        for (int i = 0; i < arraySize - (length - 1); i++) {
            marks.add(-1);      // -1 indicates unmarked
        }
        int markedCount = 0;
        
        // Loop through each index starting from the maximum
        for (IndexTracker tracker : sortedTrackers) {
            // Range of subarrays that overlap the current index
            int left = tracker.index - (length - 1);
            int right = tracker.index;

            // Marks affected subarrays with the value at the current index
            for (int i = left; i <= right; i++) {
                if (i < 0 || i >= marks.size()) {
                    continue;
                }
                if (marks.get(i) == -1) {
                    marks.set(i, tracker.value);
                    markedCount++;
                }
            }
            
            // Once all subarrays have been marked, returns the most recently used value (equivalent to the minimum)
            if (markedCount >= marks.size()) {
                return tracker.value;
            }    
        }
        
        return -1;      // Error return
    }

    public static List<Integer> solve(List<Integer> arr, List<Integer> queries) {
        List<Integer> results = new ArrayList<>(queries.size());
        
        for ( Integer query: queries ) {
            if (query == 1){
                // Special case. Just need to find the min value.
                results.add(arr.stream()
                    .mapToInt(Integer::intValue).min().getAsInt());
            } else {
                int maxIdx = -1;
                int minOfMaxs = Integer.MAX_VALUE ;
                
                for (int i=0; i<=arr.size()-query; ++i) {
                    if ( maxIdx<i) 
                        // The max value dropped out of the query windows
                        maxIdx = windowMaxIdx(arr, i, query);
                    else if ( arr.get(i+query-1)>arr.get(maxIdx) )
                        // New max value entered the query window
                        maxIdx = i+query-1;
                    
                    minOfMaxs = Math.min(arr.get(maxIdx), minOfMaxs);
                }
                
                results.add(minOfMaxs);
            }
        }
        return results ;
    }
    
    /**
     * Calulates the index of the max value within the window
     */
    private static int windowMaxIdx(List<Integer> arr, int idx, int window) {
        int maxIdx = idx;
        for ( int i=idx+1; i<idx+window;++i ) {
            if (arr.get(i) > arr.get(maxIdx))
                maxIdx=i;
        }
        return maxIdx;
    }
    

public static List<Integer> solve(List<Integer> arr, List<Integer> queries) {
        // Write your code here
        int i, j, n = arr.size();
        List <Integer> result = new ArrayList<>();
        for (Integer query : queries) {
            List <Integer> max = new ArrayList<>();
            for (i = 0; i <= n - query; i++) {
                max.add(Collections.max(arr.subList(i, i+query)));
            }
            result.add(Collections.min(max));
        }
        return result;
    }

from collections import deque

def min_of_max_in_subarrays_with_size(d, arr):
    # use sliding window to iterate through array
    dq = deque()
    candidtaes = []
    for i in range(len(arr)):
        # remove out-of-window index
        if dq and dq[0] <= i-d:
            dq.popleft()
        # before adding the current index, make sure to remove all indexes
        # indicating to value not larger than that of the current i
        # this way can make sure the maximum is in the front of queue
        while dq and arr[dq[-1]] <= arr[i]:
            dq.pop()
        dq.append(i)
        # add to max subarrays
        if i >= d-1:
            candidtaes.append(arr[dq[0]])
    return min(candidtaes)

def solve(arr, queries):
    result = []  # the min of max subarrays with size d
    for d in queries:
        result.append(min_of_max_in_subarrays_with_size(d, arr))
    return result