A94835.[POI 2014] PTA-Little Bird

有 $n$ 棵树排成一排，第 $i$ 棵树的高度是 $d_i$。

有 $q$ 只鸟要从第 $1$ 棵树到第 $n$ 棵树。

当第 $i$ 只鸟在第 $j$ 棵树时，它可以飞到第 $j+1, j+2, \cdots, j+k_i$ 棵树。

如果一只鸟飞到一颗高度大于等于当前树的树，那么它的劳累值会增加 $1$，否则不会。

由于这些鸟已经体力不支，所以它们想要最小化劳累值。

第一行输入 $n$。

第二行 $n$ 个数，第 $i$ 个数表示 $d_i$。

第三行输入 $q$。

接下来 $q$ 行，每一行一个整数，第 $i$ 行的整数为 $k_i$。

共 $q$ 行，每一行输出第 $i$ 只鸟的最小劳累值。

数据范围

$1 \le n \le 10^6$，$1 \le d_i \le 10^9$，$1 \le q \le 25$，$1 \le k_i \le n - 1$。

样例解释

树的高度序列： 4, 6, 3, 6, 3, 7, 2, 6, 5 (索引 1 到 9)

---

第一只鸟 ($k=2$)：

• 目标： 从第 1 棵树跳到第 9 棵树，每次跳跃距离 $\le 2$。
• 最优路径： $1 \to 3 \to 5 \to 7 \to 9$
  1. $1 \to 3$ (高度 $4 \to 3$)：高度下降 ($4 > 3$)，花费 0。
  2. $3 \to 5$ (高度 $3 \to 3$)：高度不降 ($3 \le 3$)，花费 1。
  3. $5 \to 7$ (高度 $3 \to 2$)：高度下降 ($3 > 2$)，花费 0。
  4. $7 \to 9$ (高度 $2 \to 5$)：高度上升 ($2 \le 5$)，花费 1。
• 总劳累值： $0 + 1 + 0 + 1 = \mathbf{2}$。

---

第二只鸟 ($k=5$)：

• 目标： 从第 1 棵树跳到第 9 棵树，每次跳跃距离 $\le 5$。
• 最优路径： $1 \to 6 \to 9$
  1. $1 \to 6$ (高度 $4 \to 7$)：可以直接跳 (距离 5)，高度上升 ($4 \le 7$)，花费 1。
  2. $6 \to 9$ (高度 $7 \to 5$)：可以直接跳 (距离 3)，高度下降 ($7 > 5$)，花费 0。
• 总劳累值： $1 + 0 = \mathbf{1}$。