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 <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long Long;

const Long INF = ((Long)1<<31) - 1;
    
class SegTree {
public:
    int m_n;
    vector<Long> m_data;

    SegTree( int n ) { Init( n ); }

    void Init( int n ) {

	m_n = 1;
	while ( m_n < n ) m_n <<= 1;

	m_data.resize( 2*m_n - 1, INF );
    }

    void Update( int k, Long val ) {

	k += m_n - 1;

	m_data[k] = val;
	
	while ( k > 0 ) {
	    k = ( k - 1 )/2;
	    m_data[k] = min( m_data[2*k+1], m_data[2*k+2] );
	}
    }

    Long RMQ( int a, int b ) {
	return query( a, b + 1, 0, 0, m_n );
    }

    void Print() const {
	for ( int i=0; i<m_data.size(); ++i ) {
	    cout << i << ": " << m_data[i] << endl;
	}
    }
protected:

    Long query( int a, int b, int k, int l, int r ) {

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

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

	Long left = query( a, b, 2*k+1, l, (l+r)/2 );
	Long right = query( a, b, 2*k+2, (l+r)/2, r );

	return min( left, right );
    }

};


int main() {

    int n, l;

    cin >> n >> l;

    SegTree seg( n );

    int a;
    for ( int i=0; i<n; ++i ) {
	cin >> a;
	seg.Update( i, (Long)a );
    }

    --l;
    for ( int i=0; i+l<n; ++i ) {
	cout << seg.RMQ( i, i+l );
	if ( i+l == n-1 ) cout << endl;
	else cout << " ";
    }
    
    return 0;
}