#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Sliding Minimum - Classic Problems | Repovive

CLS50. Sliding Minimum

2s256 MB

Given an array and a window length $k$ , print the minimum value in every contiguous window of length $k$ from left to right.

Constraints

$1 \le k \le n \le 2 \cdot 10^5$
$-10^9 \le a_i \le 10^9$

Input

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

Output

m_1 \quad m_2 \quad \ldots \quad m_{n-k+1}

Samples

Input

6 3
4 2 12 3 -1 6

Explanation

The four windows have minimum values 2, 2, -1, and -1.

Output

2 2 -1 -1

Input

4 1
8 7 6 5

Explanation

With window length 1, each answer is the single value in that window.

Output

8 7 6 5

Input

5 5
3 1 4 1 5

Explanation

There is only one full window, and its minimum value is 1.

Output

Given an array and a window length $k$ , print the minimum value in every contiguous window of length $k$ from left to right.

$1 \le k \le n \le 2 \cdot 10^5$
$-10^9 \le a_i \le 10^9$

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

m_1 \quad m_2 \quad \ldots \quad m_{n-k+1}