P2251 Quality Inspection

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.

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 $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.

[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