/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	// public static void main(String[] args) {
      
       
 //       int arr[]={1,3,-1,-3,5,3,6,7};
 //       int k=3;
 //       int l=0,r=3-l-1;
 //       List<Integer> min =new ArrayList<>();
 //       List<Integer> max =new ArrayList<>();
 //       while(l < arr.length && r< arr.length){
 //           Deque<Integer> dq = designIncresingQueue(arr,l,r);
 //           Deque<Integer> dq2 = designDecresingQueue(arr,l,r);
 //           r++;
 //           l++;
 //           min.add(arr[dq.peekFirst()]);
 //           max.add(arr[dq2.peekFirst()]);
 //       }
 //       System.out.println(min);
 //       System.out.println(max);
 //   }
 
   public static void main(String[] args) {
        int[] arr = {1,3,-1,-3,5,3,6,7};
        int k = 3; // window size

        List<Integer> min = new ArrayList<>();
        List<Integer> max = new ArrayList<>();

        Deque<Integer> minDq = new ArrayDeque<>();
        Deque<Integer> maxDq = new ArrayDeque<>();

        int l = 0;

        for (int r = 0; r < arr.length; r++) {

            // maintain increasing deque (min)
            while (!minDq.isEmpty() && arr[minDq.peekLast()] > arr[r]) {
                minDq.pollLast();
            }
            minDq.addLast(r);

            // maintain decreasing deque (max)
            while (!maxDq.isEmpty() && arr[maxDq.peekLast()] < arr[r]) {
                maxDq.pollLast();
            }
            maxDq.addLast(r);

            // window size reached
            if (r - l + 1 == k) {

                min.add(arr[minDq.peekFirst()]);
                max.add(arr[maxDq.peekFirst()]);

                // remove out of window
                if (minDq.peekFirst() == l) {
                    minDq.pollFirst();
                }
                if (maxDq.peekFirst() == l) {
                    maxDq.pollFirst();
                }

                l++;
            }
        }

        System.out.println("Min: " + min);
        System.out.println("Max: " + max);
    }
    
    public static  Deque<Integer> designIncresingQueue(int []arr,int start,int end){
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i=start;i<=end;i++){
            while(!dq.isEmpty() && arr[dq.peekLast()] > arr[i]){
                dq.pollLast();
            }
            dq.offerLast(i);
        }
        return dq;
    }
    
    public static  Deque<Integer> designDecresingQueue(int []arr,int start,int end){
        Deque<Integer> dq = new ArrayDeque<>();
        for(int i=start;i<=end;i++){
            while(!dq.isEmpty() && arr[dq.peekLast()] < arr[i]){
                dq.pollLast();
            }
            dq.offerLast(i);
        }
        return dq;
    }
}