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]). 
import java.util.*;
import java.io.*;
public class Main {
	static int[] mmax=new int[4123456];
	static int[] add=new int[4123456];
	static void pushup(int x) {
		mmax[x]=Math.max(mmax[x<<1],mmax[x<<1|1]);
	}
	static void pushdown(int x) {
		if (add[x]>0){
			mmax[x<<1]+=add[x];
			mmax[x<<1|1]+=add[x];
			add[x<<1]+=add[x];
			add[x<<1|1]+=add[x];
			add[x]=0;}
	}
	static void update(int x,int L,int R,int l,int r,int val) {
		if (l<=L&&r>=R) {
			mmax[x]+=val;
			add[x]+=val;
			return;
		}
		pushdown(x);
		int m=(L+R)>>1;
		if (m>=l) update(x<<1,L,m,l,r,val);
		if (m<r) update(x<<1|1,m+1,R,l,r,val);
		pushup(x);
	}
	//static void dfs(int u) {
	//	for (int i=0;i<G[u].size();++i) {
	//		int v=G[u].get(i);
	//		dfs(v);
	//	}
	//}
	public static void main(String[] args) throws IOException {
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		int n=(int)in.nval;
		in.nextToken();
		int k=(int)in.nval;
		int[] a=new int[n+1];
		//System.out.printf("n=%d\n",n);
		ArrayList<Integer>[] G=new ArrayList[1123456];
		for (int i=1;i<=n;++i) {
			in.nextToken();
			a[i]=(int)in.nval;
			G[i]=new ArrayList<Integer>();
		}
		int s=0;
		int[] deq=new int[n+1];
		boolean[] vis=new boolean[n+1];
		for (int i=n;i>=1;--i) {
			while (s>0&&a[deq[s-1]]<=a[i]) --s;
			if (s>0) {
				G[deq[s-1]].add(i);
				vis[i]=true;
			}
			deq[s++]=i;
		}
		int[] stk=new int[n+1];
		int[] st=new int[n+1];
		int[] ed=new int[n+1];
		int[] cur=new int[n+1];
		s=0;
		for (int i=1;i<=n;++i) if (!vis[i])
			stk[++s]=i;
		int tot=0;
		while (s>0) {
			int u=stk[s];
			if (st[u]==0) st[u]=++tot;
			if (cur[u]==G[u].size()) {
				ed[u]=tot;
				--s;
			}
			//System.out.printf("u=%d\n",u);
			while (cur[u]<G[u].size()) {
				int v=G[u].get(cur[u]);
				stk[++s]=v;
				++cur[u];
				break;
			}
		}
		for (int i=1;i<k;++i)
			update(1,1,n,st[i],ed[i],1);
		for (int i=k;i<=n;++i) {
			update(1,1,n,st[i],ed[i],1);
			out.printf("%d%c",mmax[1],i==n?'\n':' ');
			update(1,1,n,st[i-k+1],st[i-k+1],-1000000);
		}
		out.flush();
	}
}
/*
6 4
1 5 2 5 3 6
*/