#541. 疲惫的小鸟

疲惫的小鸟

题目描述

有 nn 座山排成一排,第 ii 座山的高度是 hih_i。

有 mm 只鸟要从第 11 座山到第 nn 座山。

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

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

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

你能计算出来吗?

输入格式

第一行输入 nn。

第二行 nn 个数,第 ii 个数表示 hih_i。

第三行输入 mm。

接下来 mm 行,每一行一个整数,第 ii 行的整数为 kik_i。

输出格式

共 mm 行,第 i 行输出第 ii 只鸟的最小总疲惫值。

样例输入

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

样例输出

2
1

数据范围

30% 的数据:1≤n≤101 ≤ n ≤ 10

50% 的数据:1≤n≤1001 ≤ n ≤ 100

60% 的数据:1≤n≤10001 ≤ n ≤ 1000

100% 的数据:1≤n≤1061 ≤ n ≤ 10^6,1≤hi≤1091 ≤ h_i ≤ 10^9,1≤m≤251 ≤ m ≤ 25,1≤ki≤n−11 ≤ k_i ≤ n - 1。