Description

To check the quality of a total of $N$ products on a production line, we first assign each product a score $A$ indicating its quality. Then we compute $Q_m = \min\{A_1, A_2, \cdots, A_m\}$, the score of the worst-quality product among the first $M$ products, and similarly compute the $Q_{m + 1}$ for products $2$ through $M + 1$, $Q_{m + 2}$ for products $3$ through $M + 2$, ... Finally, compute $Q_n$ for products $N - M + 1$ through $N$. We will further evaluate based on $Q$.

Please compute the sequence $Q$ as quickly as possible.

Input Format

The input contains two lines.

The first line contains two numbers $N$ and $M$, separated by a space, as described above.

The second line contains $N$ numbers, representing the quality scores of the $N$ products.

Output Format

Output $N - M + 1$ lines.

Lines $1$ through $N - M + 1$ each contain one number. On line $i$, output $Q_{i + M - 1}$, as described above.

10 4
16 5 6 9 5 13 14 20 8 12

5
5
5
5
5
8
8

Hint

[Constraints]

For $30\%$ of the testdata, $N \le 1 000$.

For $100\%$ of the testdata, $M \le N \le 10^5, A_i \le 10^6$.

Translated by ChatGPT 5