Problem: For a given array $a_1, a_2, a_3, ... , a_N$ of $N$ elements and an integer $L$, find the minimum of each possible sub-arrays with size $L$ and print them from the beginning. For example, for an array $\\{1, 7, 7, 4, 8, 1, 6\\}$ and $L = 3$, the possible sub-arrays with size $L = 3$ includes $\\{1, 7, 7\\}$, $\\{7, 7, 4\\}$, $\\{7, 4, 8\\}$, $\\{4, 8, 1\\}$, $\\{8, 1, 6\\}$ and the minimum of each sub-array is 1, 4, 4, 1, 1 respectively.

Constraints

* $1 \leq N \leq 10^6$
* $1 \leq L \leq 10^6$
* $1 \leq a_i \leq 10^9$
* $L \leq N$

Input

The input is given in the following format.

$N$ $L$
$a_1$ $a_2$ ... $a_N$

Output

Print a sequence of the minimum in a line. Print a space character between adjacent elements.

Example

Input

7 3
1 7 7 4 8 1 6


Output

1 4 4 1 1

Solution (in JAVA):

Solution:
;

import java.util.Scanner;

import static java.lang.Math.min;

public class Main {
    static final int INF = 2147483647;
    static int n;
    static int[] D;

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int l = scanner.nextInt();
        initRMQ(N);

        for(int i = 0; i < N; i++){
            int x = scanner.nextInt();
            update(i, x);
        }

        
        for(int i = 0; i <= N - l; i++){
            System.out.print(query(i, i + l, 0, 0, n));
            if(i < N - l) System.out.print(" ");
        }

        System.out.println();


    }

    public static String deleteColon(String str){
        StringBuilder sb = new StringBuilder(str);
        sb.deleteCharAt(sb.lastIndexOf(" "));
        return sb.toString();
    }

    public static void initRMQ(int l){
        n = 1;

        while (n < l){
            n *= 2;
        }

        D = new int[2 * n - 1];

        for(int i = 0; i < 2 * n - 1; i++){
            D[i] = INF;
        }

    }

    public static void update(int k, int a){
        k += n - 1;
        D[k] = a;
        while (k > 0){
            k = (k - 1) / 2;
            D[k] = min(D[k * 2 + 1], D[k * 2 + 2]);
        }
    }

    public static int findMin(int a, int b){
        return query(a, b + 1, 0, 0, n);
    }

    public static int query(int a, int b, int k, int l, int r){

        if(r <= a || b <= l) return INF;

        if(a <= l && r <= b) return D[k];


        int vl = query(a, b, k * 2 + 1, l, (l + r) / 2 );
        int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);

    }
}