【例题3】耗费体力

题目描述

跳跳虎喜欢在树林间跳跃，它从一棵较高的树跳到一棵较矮的树不需要消耗体力，否则消耗一点体力。

给出一排树，在一轮游戏的开始，跳跳虎在第$1$棵树，它要跳到第$n$棵树。每轮游戏有一个步伐限制$k$，跳跳虎只能从第$i$棵树跳到第$j$棵树（$i < j \leq i + k$），求每轮游戏最少耗费多少体力。

输入格式

第一行一个整数$n$，表示有多少棵树。

第二行$n$个整数，表示每棵树的高度。

第三行一个整数$m$，表示$m$轮游戏。

接下来$m$行，每行一个整数，表示步伐限制。

输出格式

$m$个整数，表示每次最少耗费的体力。

数据范围与提示

对于$100\%$的数据，$2 < n < 1000000$，树的高度不超过$10^{9}$，每次步伐的限制不超过$25$。

样例

9
4 6 3 6 3 7 2 6 5
2
2
5

2
1