简要题意：
给定一个数组，求所有连续 (m) 个数的最大值和最小值。
首先，对于这种题目，用 (5+) 种方法（至少），这里介绍几种吧。
算法一
根据 ( exttt{RMQ}) 算法解决问题。
用 (f_{i,j}) 表示从 (i) 开始往后 (2^j) 个的最大值。（(2^j > n) 则视为 (n)）
那么，显然有：
其中，(f_{i,j-1}) 即往后先走 (2^{j-1}) 个， 再走 (2^{j-1}) 个，类似于 倍增 算法。
然后，预处理 (log)，即可 (O(n log n)) 初始化，(O(1)) 回答。
时间复杂度：(O(n log n + k)).
期望得分：(50pts) ~ (100pts).（取决于程序常数，听说这道题目 卡任何带 (log) 的算法，不知道能不能卡过去）
算法二
分块，本题效率最慢的算法。
显然，分成 (sqrt{n}) 块，对每块分别计算，对于 (n-k+1) 个块分别询问。
时间复杂度：(O((n-k+1) sqrt{n}))， 如果是极限数据 (n=10^6)，(k=1) 就直接卡掉了。（(k) 很小就可以）
期望得分：(50pts) ~ (100pts).
实际得分：(92pts).（有人实测过，卡常得高分）
算法三
线段树，在分块与 ( ext{RMQ}) 之间。
这题的算法上有线段树但是过不了。。。
不用说了吧，模板在此.
时间复杂度：(O(n log n + k log n)). （显然被卡超时，不过：）
期望得分：(50pts) ~ (100pts).
实际得分：(92pts).（真·卡常大法好）
算法四
指令集。？？？
学习完之后，相信你能随便用一个数据结构（甚至是暴力？？？）切掉本题！
时间复杂度：(O(n^2)) ~ (O(n log n + k log n)) ~ (O(n log n + k)).
期望得分：(100pts).
实际得分：(92pts) ~ (100pts).（众所周知数据加强过一次，要是加强之前交没准就过了，不然没准被卡）
算法五
扯了这么多。。终于到正题了！
单调队列 为什么叫这么名字，它不是白叫的好吧 像平衡树要是不平衡那要它干么呢 。
假设，现在一个君王他叫做 (CCF)（(CCF = ext{Centre Code Forces})），有 (8) 名选手，她们（对，就是她）的才华值分别为：
1 3 -1 -3 5 3 6 7
她们从左往右依次是：zhk,yy,kkk,bfw,gyx,cz,wxq,rxz.
然后，他们参加 (CCF) 比赛的年龄分别为 (8) ~ (1) 岁。（嗯？没错）
(CCF) 有一个 怪癖：只要一个选手参加 (CCF) 比赛超过 (3) 年，她（？）就觉得该选手没有潜力了。
-
zhk在 (8) 岁的时候进入了，他发现没有一个人比他更厉害，所以他留下来了。 -
yy在 (7) 岁的时候也进入了 (CCF) 比赛，并把zhk踢下去，因为 (3>1).zhk想：他比我小还比我强，我退役吧，然后就退役了。 -
kkk在 (6) 岁时一来，发现被yy吊打了（(3 > -1)），但是他想：你比我强，但是我比你小，我更有潜力，我活的比你久，没准等你退役我就是老大！ 于是留了下来。然后，( ext{CCF Round 1}) 冠军产生：yy. -
bfw一看：嗯？怎么前面的人都比我强啊？事实然后他觉得，自己留下来的时间更久，等她们都退役再说。 于是留了下来。( ext{CCF Round 2}) 冠军产生：yy. -
gyx来了之后，他发现自己是最强的 (5>3)，然后所有的人（除了她）都觉得 有人比我小还比我强，集体退役。yy又遭到 (CCF) 的潜力质疑，精神病发作了。( ext{CCF Round 3}) 冠军产生：gyx. -
cz来了之后，嗯发现自己是最弱的，但是她想： CCF质疑gyx比我前，所以我比她活得长！活得长就是报仇，所以要留下来！( ext{CCF Round 4}) 冠军产生：gyx. -
wxq一到，瞬间 吊打集训队，吊打全场然后gyx和cz一起退役了。( ext{CCF Round 5}) 冠军产生：wxq. -
最后
rxz到了，结束了wxq的 (CCF) 生涯，把她弄自闭然后滚出集训队了。（我才不会告诉你） ( ext{CCF Round 6}) 冠军产生：rxz就是 (CCF) 出题人rxz.
若干年过去了，( ext{CCF}) 决定：分数越低的人得奖越高，那些强者实在弱不下来，于是又开始了第二场 互逼退役 的旅程。。
综上可见，单调队列的过程本质就是一个维护队列的过程，参加 (CCF) 则入队，退役则出队。
显然，如果用系统的 ( ext{queue}) 写会多出一个 (log)，然后变成 (O(n log n)) 级别，沦为和上述数据结构一样的。（智商不够，数据结构来凑）
所以今天我们用 手写队列，用 (l,r) 指针维护当前在队列中的元素。
时间复杂度：(O(n + k )).
实际得分：(100pts).
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
int n,m,a[N];
int q[N],p[N]; //q[i] 记录数值 , p[i] 记录编号
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
// for(int i=1;i<=n;i++) printf("%d ",a[i]); puts("");
int l=1,r=0;
for(int i=1;i<=n;i++) {
while(l<=r && q[r]>=a[i]) r--; //新来的人先吊打掉一波
q[++r]=a[i]; p[r]=i;
while(p[l]<=i-m) l++; //被质疑的可以直接退役
// printf("%d %d
",l,r);
if(i>=m) printf("%d ",q[l]);
} puts(""); l=1;r=0;
for(int i=1;i<=n;i++) {
while(l<=r && q[r]<=a[i]) r--;
q[++r]=a[i]; p[r]=i;
while(p[l]<=i-m) l++;
if(i>=m) printf("%d ",q[l]);
} //这边同理
return 0;
}