You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

有 m 只鸟，每只小鸟的飞跃距离最远为ki，就是说当第 i 只鸟在第 j 棵树时，它可以飞到第 j+1, j+2, ......, j+ki 棵树。如果一只鸟飞到一颗高度大于等于当前树的树，那么它的疲劳值会增加 1，否则不会。

请你编程求解这m只小鸟从第 1 棵树到第 n 棵树的最小化疲劳值分别是多少？

##输入格式

第一行输入 n。

第二行 n 个数，第 i 个数表示 hi。

第三行输入 m。

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

输出格式

共 m 行，每一行输出第 i 只鸟的最小疲劳值。

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

2
1

【测试数据2见文件bird2.in/bird2.out】

数据范围

对于30%的数据：N≤100，1≤q≤25，树高度在10^9之内

对于60%的数据：N≤1000，1≤q≤25，树高度在10^9之内

对于80%的数据：N≤10^5，1≤q≤25，树高度在10^9之内

对于100%的数据：1≤n≤10^6，1≤q≤25，树高度在10^9之内