题目描述

有 $n$ 座山排成一排，第 $i$ 座山的高度是 $h_i$。

有 $m$ 只鸟要从第 $1$ 座山到第 $n$ 座山。

当第 $i$ 只鸟在第 $j$ 座山时，它下一次可以飞到第 $j+1, j+2, \cdots, j+k_i$ 座山中的某一座。

如果一只鸟飞到一座高度不低于当前山的山，那么它的疲惫值会增加 $1$。

每只鸟都想知道如何飞翔才能使自己到达第 $n$ 座山时增加的总疲惫值最小。

你能计算出来吗？

输入格式

第一行输入 $n$。

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

第三行输入 $m$。

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

输出格式

共 $m$ 行，第 i 行输出第 $i$ 只鸟的最小总疲惫值。

样例输入

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

样例输出

2
1

数据范围

30% 的数据：$1 ≤ n ≤ 10$

50% 的数据：$1 ≤ n ≤ 100$

60% 的数据：$1 ≤ n ≤ 1000$

100% 的数据：$1 ≤ n ≤ 10^6$，$1 ≤ h_i ≤ 10^9$，$1 ≤ m ≤ 25$，$1 ≤ k_i ≤ n - 1$。