4. 滑动窗口

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = bf.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);
        arr = bf.readLine().split(" ");
        LinkedList<Integer> max = new LinkedList<>();
        LinkedList<Integer> min = new LinkedList<>();
        int[] maxAns = new int[n];
        int[] minAns = new int[n];
        int[] nums = new int[n];
        for (int i = 0; i < n; i++){
            nums[i] = Integer.parseInt(arr[i]);
        }
        for (int i = 0; i < n; i++){
            while (! max.isEmpty() && nums[max.peekLast()] <= nums[i]){
                max.removeLast();
            }
            while (! min.isEmpty() && nums[min.peekLast()] >= nums[i]){
                min.removeLast();
            }
            max.offer(i);
            min.offer(i);
            if (max.peek() <= i - m){
                max.removeFirst();
            }
            if (min.peek() <= i - m){
                min.removeFirst();
            }
            if (max.isEmpty()){
                maxAns[i] = -1;
            }
            else{
                maxAns[i] = nums[max.peek()];
            }
            if (min.isEmpty()){
                minAns[i] = -1;
            }
            else{
                minAns[i] = nums[min.peek()];
            }
        }
        for (int i = m - 1; i < n; i++){
            System.out.print(minAns[i] + " ");
        }
        System.out.println("");
        for (int i = m - 1; i < n; i++){
            System.out.print(maxAns[i] + " ");
        }
        System.out.println("");

    }
}