P1886 Sliding Window / [Template] Monotonic Queue

There is a sequence $a$ of length $n$ and a window of size $k$. The window slides from left to right, moving one position at a time. After each slide, find the minimum and maximum values within the window. For example, for the sequence $[1,3,-1,-3,5,3,6,7]$ and $k = 3$, the process is as follows: $$\def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{Window position} & \textsf{Minimum} & \textsf{Maximum} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array} $$

The input has two lines. The first line contains two positive integers $n, k$. The second line contains $n$ integers representing the sequence $a$.

Output two lines. The first line contains the minimum of the window after each slide. The second line contains the maximum of the window after each slide.

[Constraints] For 50% of the testdata, $1 \le n \le 10^5$. For 100% of the testdata, $1 \le k \le n \le 10^6$, $a_i \in [-2^{31}, 2^{31})$. Translated by ChatGPT 5