题目描述

比特国的森林里有 $n$ 棵排成一行的树，依次编号为 $1$ 到 $n$。一只小鸟停在第 $1$ 棵树的树顶，想飞到第 $n$ 棵树的树顶。

小鸟的体力有限，不能一定一口气飞到终点。对于体力参数为 $k$ 的小鸟，如果它当前停在第 $i$ 棵树上，一次可以飞到编号为 $i+1,i+2,\ldots,\min(i+k,n)$ 的任意一棵树上，落下后休息。

向上飞比向下飞更累。如果一次飞行的终点树高度大于或等于起点树高度，这次飞行就是一次“费力的飞行”；如果终点树更矮，则不费力。注意：飞到相同高度的树上也算费力。

你需要选择沿途停靠的树，使小鸟从第 $1$ 棵树飞到第 $n$ 棵树时，费力的飞行次数最少。

小鸟还有一些朋友也要完成这段旅程。不同小鸟的体力不同，对应不同的 $k$。请分别求出它们最少需要进行多少次费力的飞行。

输入格式

第一行一个整数 $n$，表示树的数量，$2\le n\le 10^6$。

第二行 $n$ 个整数 $d_1,d_2,\ldots,d_n$，其中 $d_i$ 表示第 $i$ 棵树的高度，$1\le d_i\le 10^9$。

第三行一个整数 $q$，表示需要规划路线的小鸟数量，$1\le q\le 25$。

接下来 $q$ 行，每行一个整数 $k_i$，表示第 $i$ 只小鸟一次飞行最多可以向右前进 $k_i$ 棵树的编号距离，$1\le k_i\le n-1$。换句话说，一次飞行最多可以越过中间的 $k_i-1$ 棵树。

输出格式

输出 $q$ 行。第 $i$ 行输出第 $i$ 只小鸟从第 $1$ 棵树到第 $n$ 棵树所需的最少费力飞行次数。

样例输入 1

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

样例输出 1

2
1

样例输入 2

2
2 1
1
1

样例输出 2

0

样例输入 3

3
1 1000000000 1
2
1
2

样例输出 3

1
1