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 CPP):

Solution:
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;

const int inf = 2147483647;
/*
 n : 葉の数
 N : 全ノードの数
 D[] : 木構造をリストで表現したもの
*/

class Segment_Tree{
private:
  int N;
  vector<int> D;
public:
  Segment_Tree(int n){
    N = 1;
    while(N < n) N *= 2;
    D.resize(2*N-1);
    for(int i=0;i<2*N-1;++i){
      D[i] = inf;
    }
  }
  
  void update(int k,int x){
    k += N - 1;
    D[k] = x;
    while(k > 0){
      k = (k-1)/2;
      D[k] = min(D[k*2+1],D[k*2+2]);
    }
  }
  
  int findMin(int a,int b){
    return query(a,b+1,0,0,N);
  }
  
  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 m = (l+r)/2;
    return min(query(a,b,2*k+1,l,m),query(a,b,2*k+2,m,r));    
  }
};

int main(){
  int n;
  int WINDOW;
  int start,end;
  
  // 一列目読み込み
  scanf("%d %d",&n,&WINDOW);
  // セグメントツリー初期化
  Segment_Tree st(n);
  int* array = new int[n+1];
  // 二列目読み込み
  for(int i = 0; i < n; i++)scanf("%d",&array[i]);
  
  // ここから事前処理
  // WINDOWサイズ分あらかじめ入れておく
  for(int i=0; i < WINDOW; i++) st.update(i, array[i]);
    
  int result;
  result = st.findMin(0,WINDOW);
  printf("%d",result);
  if (n != WINDOW){
      printf(" ");
  }else{
      printf("\n");
  }
  // 事前処理終わり

  for (int i = WINDOW; i < n; i++){
      st.update(i,array[i]);
      
      // 最小値求める範囲
      start = i - WINDOW;
      end = WINDOW + (i - WINDOW);

      result = st.findMin(start+1, end);
      printf("%d",result);
      if(i != n-1){
        printf(" ");
      }else{
          printf("\n");
      }
  }
  
  
  
 
  return 0;
}