Jisoo

显然满足单调性，可以用单调队列优化

但是要维护两个值

考虑一下这两个值来说，因为每次疲劳值最多加1，那么无论如何优先选择疲劳值最小的来进行转移，

答案肯定不会更差

如果有两个数疲劳值相同但是高度不一样的话，显然保留高度更高的比较好

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
int a[1000001];
int f[1000001];
deque<int> d;
int n;
int q;
int x;
int main(){
    std::ios::sync_with_stdio(false);
    cin>>n; 
    for(int i=1;i<=n;++i){
        cin>>a[i];
    }
    cin>>q;
    while(q--){
        cin>>x;
        while(!d.empty()){
            d.pop_back();
        }
        f[1]=0;
        d.push_back(1);
        for(int i=2;i<=n;++i){
            while(!d.empty()&&i-d.front()>x){
                d.pop_front();
            }
            f[i]=f[d.front()]+(a[d.front()]<=a[i]);
            while(!d.empty()&&(f[d.back()]>f[i]||(f[d.back()]==f[i]&&a[i]>=a[d.back()]))){
                d.pop_back();
            }
            d.push_back(i);
        }
        cout<<f[n]<<endl; 
    }
    return 0;
}