Description：

从 $1$ 开始跳到比当前矮的不消耗体力，否则消耗一点体力，每次询问有一个步幅限制，求每次最少耗费多少体力。

$1\leqslant n\leqslant10^6,1\leqslant q\leqslant 25$

Solution：

很容易想到单调队列优化 $DP$ ，但是有高度就没法做了。

但是这题一个只有一的贡献，也就是说在不考虑高度的情况下，如果一个的值严格小于另一个，那另一个一定是没用的，因为就算能省一个也不会比那个更优，也就是说只有在 $dp$ 值相同的情况下高度才会产生作用，那就还是单调队列，在 $dp$ 值相同时按高度从小到大排序就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1000010

int q[MAXN],head,tail;

struct tree

{

	int h,f;

	bool operator < (const tree &b)const

	{

		if(f != b.f)return f < b.f;

		return h < b.h;

	}

}t[MAXN];

int calc(int k)

{

	head = 1;tail = 0;

	q[++tail] = n;

	for(int i = n - 1;i >= 1;--i)

	{

		if(q[head] > i + k)++head;

		t[i].f = t[q[head]].f + (t[i].h <= t[q[head]].h);

		while(head <= tail && t[i] < t[q[tail]])--tail;

		q[++tail] = i;

	}

	return t[1].f;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&t[i].h);

	scanf("%d",&m);

	int k;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&k);

		printf("%d\n",calc(k));

	}

	return 0;

}