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 GreedySubsequences {
    static int[] eulerIn;
    static int[] eulerOut;
    static int[][] graph;
    static int eulerVal;
    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        int[] degrees = new int[N+1];
        int[] vals = new int[N];
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for(int i = 0; i < N; i++) {
            vals[i] = scanner.nextInt();
        }
        for(int i= N-1; i >= 0; i--) {
            while(!stack.isEmpty() && vals[stack.peek()] <= vals[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) degrees[N]++;
            else degrees[stack.peek()]++;
            stack.push(i);
        }
        stack.clear();
        graph = new int[N+1][];
        for(int i = 0; i <= N; i++) {
            graph[i] = new int[degrees[i]];
        }
        int[] p = new int[N+1];
        for(int i = N-1; i >= 0; i--) {
            while(!stack.isEmpty() && vals[stack.peek()] <= vals[i]) {
                stack.pop();
            }
            if (stack.isEmpty()) graph[N][p[N]++] = i;
            else graph[stack.peek()][p[stack.peek()]++] = i;
            stack.push(i);
        }
        stack.clear();
        eulerIn = new int[N+1];
        eulerOut = new int[N+1];
        eulerVal = 0;
        dfs(N);
        SegTree segTree = new SegTree(N+1, 0, N);
        for(int i = 0; i < K-1; i++) {
//            segmentTree.update_range(eulerIn[i], eulerOut[i], 1);
            segTree.increment(eulerIn[i], eulerOut[i], 1);
        }
        for(int i = K-1; i < N; i++) {
//            segmentTree.update_range(eulerIn[i], eulerOut[i], 1);
            segTree.increment(eulerIn[i], eulerOut[i], 1);
            out.print(segTree.maximum(1, N) + " ");
//            out.print(segmentTree.query(1, N+1) + " ");
            segTree.increment(eulerIn[i-K+1], eulerOut[i-K+1], -1);
//            segmentTree.update_range(eulerIn[i-K+1], eulerOut[i-K+1], -1);
        }
        out.println();
        out.flush();
    }
    public static void dfs(int v) {
        eulerIn[v] = eulerVal++;
        for(int edge: graph[v]) dfs(edge);
        eulerOut[v] = eulerVal-1;
    }
    
    public static class SegTree {
        int[] delta, max;
        int[] hi, lo;
        int size;
        public SegTree(int ss, int l, int r) {
            size = ss;
            delta = new int[4*ss+1];
            max = new int[4*ss+1];
            hi = new int[4*ss+1];
            lo = new int[4*ss+1];
            init(l, r, 1);
        }
        public void init(int l, int r, int cur) {
            lo[cur] = l;
            hi[cur] = r;
            if (l==r) return;
            int mid = (l+r)/2;
            init(l, mid, cur*2);
            init(mid+1, r, cur*2+1);
        }
        public void increment (int l, int r, int inc) {
            increment(l, r, inc, 1);
        }
        public void increment(int l, int r, int inc, int cur) {
            if (r < lo[cur] || l > hi[cur]) return;
            if (r >= hi[cur] && l <= lo[cur]) {
                delta[cur] += inc;
                return;
            }
            prop(cur);
            increment(l, r, inc, cur*2);
            increment(l, r, inc, cur*2+1);
            update(cur);
        }
        public long maximum (int l, int r) {
            return maximum(l, r, 1);
        }
        public long maximum(int l, int r, int cur) {
            //no coverage case
            if (r < lo[cur] || l > hi[cur]) return Integer.MIN_VALUE;
            //total coverage
            if (r >= hi[cur] && l <= lo[cur]) return max[cur] + delta[cur];
            prop(cur);
            long left = maximum(l, r, cur*2);
            long right = maximum(l, r, cur*2+1);
            update(cur);
            return Math.max(left, right);
        }
        public void prop(int cur) {
            delta[cur*2] += delta[cur];
            delta[cur*2+1] += delta[cur];
            delta[cur] = 0;
        }
        public void update(int cur) {
            max[cur] = Math.max(max[cur*2] + delta[cur*2], max[cur*2+1] + delta[cur*2+1]);
        }
        
    }
    
    
    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
        
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
    }
}
