Description

Given a sequence with $n$ terms, for each term, find the minimum within the interval consisting of the previous $m$ numbers before it. If there are fewer than $m$ previous numbers, start from the first number. If there are no previous numbers, output $0$.

Input Format

The first line contains two integers $n$, $m$.

The second line contains $n$ positive integers, which form the given sequence $a_i$.

Output Format

Output $n$ lines, one integer per line. The $i$-th number is the minimum among the $m$ numbers before $a_i$ in the sequence.

6 2
7 8 1 4 3 2

0
7
7
1
1
3 

Hint

For $100\%$ of the testdata, it is guaranteed that $1 \le m \le n \le 2\times 10^6$, $1 \le a_i \le 3\times 10^7$.

Translated by ChatGPT 5