For some array c, let's denote a greedy subsequence as a sequence of indices p_1, p_2, ..., p_l such that 1 ≤ p_1 < p_2 < ... < p_l ≤ |c|, and for each i ∈ [1, l - 1], p_{i + 1} is the minimum number such that p_{i + 1} > p_i and c[p_{i + 1}] > c[p_i].

You are given an array a_1, a_2, ..., a_n. For each its subsegment of length k, calculate the length of its longest greedy subsequence.

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 10^6) — the length of array a and the length of subsegments.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n) — array a.

Output

Print n - k + 1 integers — the maximum lengths of greedy subsequences of each subsegment having length k. The first number should correspond to subsegment a[1..k], the second — to subsegment a[2..k + 1], and so on.

Examples

Input


6 4
1 5 2 5 3 6


Output


2 2 3 


Input


7 6
4 5 2 5 3 6 6


Output


3 3 

Note

In the first example: 

  * [1, 5, 2, 5] — the longest greedy subsequences are 1, 2 ([c_1, c_2] = [1, 5]) or 3, 4 ([c_3, c_4] = [2, 5]). 
  * [5, 2, 5, 3] — the sequence is 2, 3 ([c_2, c_3] = [2, 5]). 
  * [2, 5, 3, 6] — the sequence is 1, 2, 4 ([c_1, c_2, c_4] = [2, 5, 6]). 



In the second example: 

  * [4, 5, 2, 5, 3, 6] — the longest greedy subsequences are 1, 2, 6 ([c_1, c_2, c_6] = [4, 5, 6]) or 3, 4, 6 ([c_3, c_4, c_6] = [2, 5, 6]). 
  * [5, 2, 5, 3, 6, 6] — the subsequence is 2, 3, 5 ([c_2, c_3, c_5] = [2, 5, 6]). 
//created by Whiplash99
import java.io.*;
import java.util.*;
public class G
{
    private static int tin[], tout[], timer=1;
    private static ArrayDeque<Integer> edge[];
    static class Segtree  //max query with range updates
    {
        int N, max[], delta[];
        Segtree(int NN){N=NN;max=new int[4*N];delta=new int[4*N];}
        int func(int a, int b){return Math.max(a,b);}
        void prop(int i){delta[2*i+1]+=delta[i]; delta[2*i+2]+=delta[i]; delta[i]=0;}
        void fix(int i){max[i]=func(max[2*i+1]+delta[2*i+1],max[2*i+2]+delta[2*i+2]);}
        void update(int a, int b, int val){update(0,0,N-1,a,b,val);}
        void update(int i, int l, int r, int a, int b, int val)
        {
            if(r<a||b<l) return;
            if(a<=l&&r<=b) { delta[i]+=val; return;}

            prop(i);
            int m=(l+r)/2;
            update(2*i+1,l,m,a,b,val);
            update(2*i+2,m+1,r,a,b,val);
            fix(i);
        }
        int query(){return max[0]+delta[0];}
    }
    private static void DFS(int u)
    {
        ArrayDeque<Integer> stack=new ArrayDeque<>();
        stack.push(u);

        while (!stack.isEmpty())
        {
            u=stack.peek();
            if(tin[u]==0) tin[u]=timer++;
            else
            {
                stack.pop();
                tout[u]=timer-1;
                continue;
            }
            while (!edge[u].isEmpty())
            {
                int v=edge[u].poll();
                if(tin[v]==0) stack.push(v);
            }
        }
    }
    public static void main(String[] args) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int i,N;

        String s[]=br.readLine().trim().split(" ");
        N=Integer.parseInt(s[0]);
        int K=Integer.parseInt(s[1]);

        s=br.readLine().trim().split(" ");
        int a[]=new int[N+5];
        for(i=0;i<N;i++) a[i]=Integer.parseInt(s[i]);
        a[N]=N+5;

        edge=new ArrayDeque[N+5];
        tin=new int[N+5]; tout=new int[N+5];
        for(i=0;i<=N;i++) edge[i]=new ArrayDeque<>();

        ArrayDeque<Integer> stack=new ArrayDeque<>();
        for(i=0;i<=N;i++)
        {
            while (!stack.isEmpty()&&a[i]>a[stack.peek()])
            {
                edge[i].add(stack.peek());
                edge[stack.pop()].add(i);
            }
            stack.push(i);
        }

        DFS(N);
        Segtree ST=new Segtree(tout[N]+1);
        StringBuilder sb=new StringBuilder();

        for(i=0;i<K;i++) ST.update(tin[i], tout[i],1);
        sb.append(ST.query()).append(" ");

        for(i=K;i<N;i++)
        {
            ST.update(tin[i-K], tout[i-K], -1);
            ST.update(tin[i], tout[i], 1);
            sb.append(ST.query()).append(" ");
        }

        System.out.println(sb);
    }
}