对于这道题可以很容易写出状态转移方程。但直接转移会超时，所以需要单调队列优化。这里的单调队列采取左闭右开写法，容易理解。
怎么做呢？常规取出队头决策就不多说了。怎么判断当前决策是否更优呢？当状态较优秀且树高比较高，就可以考虑去掉尾巴。
代码：
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define fo(i,a,b) for(int i=(a);i<(b);++i)
using namespace std;
const int N=1e6+5;
int d[N],n;
int f[N],q[N];
void solve(int k){
memset(f,0x3f,sizeof f);
int hh=0,tt=0;
f[1]=0;
q[tt++]=1;
for(int i=2;i<=n;i++){
while(hh<tt&&i-q[hh]>k) hh++;
if(hh<tt) {
if(d[q[hh]]>d[i]) f[i]=f[q[hh]];
else f[i]=f[q[hh]]+1;
}
while(hh<tt&& ( f[i]<f[q[tt-1]]|| (f[i]==f[q[tt-1]]&&d[i]>=d[q[tt-1]]) )) tt--;
q[tt++]=i;
}
cout<<f[n]<<'\n';
}
int main(){
cin>>n;
rep(i,1,n) cin>>d[i];
int Q;
cin>>Q;
rep(kase,1,Q){
int k;
cin>>k;
solve(k);
}
}