有长度为 $n$ 的数组 $C$（编号为 $0\sim n-1$）和窗口大小 $K$，

你要求出数组中每个长度为 $K$ 的连续子数组的最小值，你需要按顺序输出这 $n-K+1$ 个值。

数组 $C$ 将被遍历两次，每遍历到一个元素会将其作为参数 $val$，调用 helpBessie(val)。

你需要实现函数 void helpBessie(int x)，你可以用函数 void shountMinimum(int x) 按顺序汇报答案。特别地，我们并不要求每次 helpBessie 恰好汇报 $1$ 次答案。

你在函数的两次调用之间只能使用题目提供的寄存器存储 $5500$ 个 $32$ 位有符号整数，位置编号为 $0\sim 5499$，最初每个寄存器均存储了 $0$，用 set(x) 存储，get(x) 读取，要求 set、get 的调用总次数不超过 $2.5\times 10^7$ 次。

$n\le 10^6,K\le n$。

首先如果没有特殊的空间限制那么就是单调队列模板题，单调队列的空间复杂度是 $\mathcal{O}(K)$。

我们发现题目的数组将会被遍历 $2$ 遍，

那我们应该在第 $1$ 遍遍历的时候预处理一些信息并存储下来，并在第 $2$ 遍遍历时求出准确答案。

考虑这些信息需要起到什么作用，要求我们不再需要存储 $\mathcal{O}(K)$ 个单调递增的数，于是我们希望提前知道一些位置的窗口最小值，但是位置不能太多，于是我们考虑根号平衡，每隔 $\mathcal{O}(\sqrt{n})$ 个数存一个答案，一共存下 $\mathcal{O}(\sqrt{n})$ 个。

我们考虑对序列分块，令 $B=\sqrt{n},num=\lfloor\frac{n}{B}\rfloor$，块编号从 $0$ 开始，第 $i$ 个位置所在的块编号为 $\lfloor\frac{i}{B}\rfloor$（为了方便表述我们定义 $id_i=\lfloor\frac{i}{B}\rfloor,L_i=i\cdot B,R_i=(i+1)\cdot B-1$，代码中实际并未定义这些量）。

记我们当前传入的位置为 $ps$，传入的参数为 $val$，有 $C_{ps}=val$，

在第 $1$ 遍遍历时求出对于 $i\in [1,n]$，以第 $i$ 个块的第一个位置 $L_i$ 开头的长度为 $K$ 的区间的最小值的最早位置 $f_i$。

具体地，我们记录每一块截至 $ps$ 位置的最小值 $mn_i$ 以及最小值的位置 $pos_i$（所以 $id_{ps}$ 后面的块都是 $\infty$，$id_{ps}$ 只记录了 $[L_{id_{ps}},ps]$ 区间的最小值），分别存储在寄存器的 $0\sim num/(0+(num+1))\sim (num+(num+1))$ 位置。

设我们当前计算到第 $i$ 块的 $f_i$，若 $ps=\min(L_i+k-1,n)$，那么此时可以计算 $f_i$，我们发现 $f_i$ 就是 $[i,id_{ps}]$ 区间的 $mn_i$ 中取最小的且 $pos_i$ 位置最前的，我们将 $f_i$ 存储在 $(0+C)\sim (num+C)$（这里的 $C\approx 2B$ 但是比 $2B$ 大，原因后面讲，是为了方便储存第 $2$ 遍遍历）。

然后我们在第 $2$ 遍遍历的时候求答案，

我们维护一个单调队列，头尾指针分别为 $l,r$，

我们将当前 $val$ 加入单调队列，队列中记录每个数的值 $v_i$ 以及位置 $p_i$（值 $v_i$ 是单调递增的），分别循环存储在寄存器的 $0\sim S-1/(0+S)\sim (S-1)+S$ 位置，从 $l\bmod S$ 循环到 $r \bmod S$，其中 $S$ 定义为单调队列中同时存在的数的数量最大值。

设我们当前算到的起始位置为 $i$，若有 $ps=i+k-1$ 或 $ps=f_{id_i+1}$（要么区间长度等于 $k$ 要么已经出现在 $[L_{id_i+1},L_{id_i+1}+k-1]$ 区间的最小值，显然 $i$ 开头的不可能取到比这更小的值了），那么说明 $i$ 能取到最小值已经出现，我们将位置 $p$ 小于 $i$ 的队列元素弹出，然后输出队列开头的 $v$ 即可。

下证 $S$ 不超过 $B+1$。

在任意时刻，对于当前在计算的起始位置 $i$，单调队列的元素可以划分为属于 $id_i$ 块的元素和属于 $>id_i$ 块的元素（不妨称为当前块和后续块的集合），

• 对于当前块，块长为 $B$，在当前块元素单调递增时，块中所有元素都在队列中，最多有 $B$ 个。

• 对于后继块的集合，若有多于 $1$ 个后继块集合中的元素（显然这些元素也满足单调递增），我们可以选择只保留元素最小且位置最前的那个，其余的全部弹出。

  我们证明为什么只保留 $1$ 个是正确的，

  假设我们同时有两个后继块元素，设这两个数为 $A,B$，满足 $A<B$ 且 $A$ 在 $B$ 前面（$A$ 是先前保留的最小元素，$B$ 是当前新加入的）.

  那么当我们计算答案时，$A,B$ 均属于区间 $[L_{id_i+1},L_{id_i+1}+k-1]$，

  我们发现因为我们预处理了 $f$，所以当 $ps$ 遍历到 $A$ 的时候（显然 $ps$ 会先遍历 $A$ 再遍历 $B$），有两种情况：

  • 若有 $C_{f_i}=A$，我们会将 $A$ 可以贡献到的 $i$ 全部贡献掉，此时 $i$ 来到 $A$ 所在块，$ps$ 遍历到 $B$ 时，若 $A,B$ 同块，那么 $B$ 成为了当前块元素，不会被弹出，否则 $B$ 会作为唯一后继块元素被保留。
  • 否则 $C_{f_i}\not =A$，既然 $A$ 都不是后继块长度为 $K$ 的区间的最小值，那么 $>A$ 的 $B$ 更不可能成为后继块的最小值（因为在 $A$ 失效后会出现比 $A$ 小的 $C_{f_i}$，且 $C_{f_i}$ 在 $B$ 后面），将 $B$ 弹出。

  综上 $A,B$ 不会同时存在。

然后因为 $S$ 涉及取模操作所以我们取 $S=1024$ 来提高效率，所以上文取 $C=2S+1$，其他就和普通的单调队列是一致的。

时间复杂度是 $\mathcal{O}(n)$ 的，空间复杂度是 $\mathcal{O}(\sqrt{n})$ 的，带 $3$ 倍常数，可以通过此题。

#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
using namespace std;

int get(int);
void set(int,int);
void shoutMinimum(int);
int getTrainLength();
int getWindowLength();
int getCurrentCarIndex();
int getCurrentPassIndex();

void helpBessie(int val){
	int ps=getCurrentCarIndex(),n=getTrainLength()-1,k=getWindowLength();
	int inf=2e9,B=1000,num=n/B,S=1024,C=(S<<1)+1;
	if(!getCurrentPassIndex()){
		if(!ps) FL(i,0,num) set(i,inf);
		if(val<get(ps/B)) set(ps/B,val),set(ps/B+(num+1),ps);
		int i=get(5499);
		while(i<=n/B&&(ps==i*B+k-1||ps==n)){
			int mn=inf,pos=0;
			FL(j,i,ps/B){
				int tmp=get(j);
				if(tmp<mn) mn=tmp,pos=get(j+(num+1));
			}
			set(i+C,pos);
			i++;
		}
		set(5499,i);
	}
	else{
		if(!ps) set(5496,0),set(5497,1),set(5498,0),set((n/B+1)+C,-1);
		int i=get(5496),l=get(5497),r=get(5498);
		while(l<=r&&val<=get(r%S)) r--;
		r++,set(r%S,val),set(r%S+S,ps);
		while(i+k-1<=n&&(ps==i+k-1||ps==get((i/B+1)+C))){
			while(l<=r&&get(l%S+S)<i) l++;
			shoutMinimum(get(l%S));
			i++;
		}
		if(l<=r-1&&ps/B>i/B&&get((r-1)%S+S)/B>i/B) r--;
		set(5496,i),set(5497,l),set(5498,r);
	}
}