g5-08306. 窗口里的最大值 未做

读入 $n$ 个整数和一个窗口长度 $k$。窗口从序列最左端开始，每次向右滑一格，共得到 $n-k+1$ 个窗口；对每个窗口输出其中的最大值。

$n$ 与 $k$ 都不小，逐个窗口扫 $k$ 个数会超时。可以用单调双端队列：队列里存下标，并让这些下标对应的值从队头到队尾递减——新元素进队尾前，先把队尾所有值不大于它的下标弹掉（它们不可能再成为任何窗口的最大值）；队头下标一旦滑出窗口范围，就把它从队头弹掉。这样每个元素最多进出队一次，每个窗口的答案就是队头下标对应的值。

第一行两个整数 $n$、$k$（$1\le k\le n\le 2\times 10^5$）。

第二行 $n$ 个整数 $a_i$（$-10^9\le a_i\le 10^9$）。

一行 $n-k+1$ 个整数：依次为每个窗口的最大值，用空格分隔。

输入：

8 3
1 3 -1 -3 5 3 6 7

输出：

3 3 5 5 6 7

六个窗口的最大值依次是 3、3、5、5、6、7，例如第 4 个窗口 $[-3,5,3]$ 里最大是 5。

$1\le k\le n\le 2\times 10^5$。单调队列从头到尾「递减」，队头才是最大值——方向存成「递增」，队头就变成了最小值。