题目描述

题目译自 XXI Olimpiada Informatyczna — II etap Ptaszek

在字节森林中，$n$ 棵树木排成一列。一只小鸟站在第一棵树的树梢，想飞到最后一棵树的顶端。它还年幼，体力有限，可能无法一口气飞完全程。若小鸟在第 $i$ 棵树的树梢，它一次飞行可到达第 $i+1, i+2, \ldots, i+k$ 棵树，之后必须停下休息。

向上飞对小鸟来说格外吃力：从较低或等高的树飞到更高或等高的树会让它疲惫不堪，而向下飞则轻松无忧。你需要为小鸟规划落脚的树木，让它尽可能少地感到疲惫。此外，小鸟有几位朋友也想从第一棵树飞到最后一棵树，它们的体力各不相同（即 $k$ 值不同）。请你也帮帮它们！

输入格式

输入第一行包含一个整数 $n$ $(2 \leq n \leq 1000000)$，表示字节森林的树木数量。

第二行包含 $n$ 个整数 $d_{1}, d_{2}, \ldots, d_{n}$ $(1 \leq d_{i} \leq 10^{9})$，$d_{i}$ 表示第 $i$ 棵树的高度。

第三行包含一个整数 $q$ $(1 \leq q \leq 25)$，表示需要考虑飞行的鸟儿数量。

接下来的 $q$ 行描述鸟儿，每行一个整数 $k_{i}$ $(1 \leq k_{i} \leq n-1)$，表示第 $i$ 只鸟儿的体力，即它一次飞行最多可跳过的树木数为 $k_{i}$。

输出格式

输出 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 只鸟儿最少需要从较低或等高树飞到更高或等高树的次数。

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

2
1

第一只鸟儿可依次停在 $1, 3, 5, 7, 8, 9$ 号树，需在第 $3$ 到第 $5$ 棵树和第 $7$ 到第 $8$ 棵树向上飞，共疲惫 $2$ 次。

附加样例

1. $n=11, q=1, k_{1}=5$，所有树高相等，答案为 $2$（在第 $6$ 棵树中途休息即可）；
2. $n=100, q=2, k_{1}=5, k_{2}=6$，树高交替为 $1$ 和 $2$，两种鸟儿每 $5$ 棵树休息一次，各疲惫 $11$ 次；
3. $n=100, q=1, k_{1}=10$，树高为 $100, 99, \ldots, 1$，答案为 $0$；
4. $n=1000000, q=25, k_{i}=i$，$d_{1000}=d_{2000}=d_{3000}=\ldots=d_{1000000}=2$，其余 $d_{i}=1$。

数据范围与提示

对于 $70\%$ 的数据，$n \leq 100000$。
对于其中 $30\%$ 的数据，$n \leq 1000$。