The Little Bird

Behind Gyeonggi Science High School there is a forest of $n$ trees standing in a row. On the first tree sits a little bird that wants to get to the top of the last tree. The bird is very small, so a single flight covers a limited distance. If the bird is on tree $i$, one flight takes it to one of the trees $i+1, i+2, \dots, i+k$, and it cannot reach any tree farther away than that.

Climbing to a taller tree costs the little bird more effort than dropping to a shorter one. The bird feels tired whenever it flies to a tree whose height is equal to or greater than the height of the tree it is sitting on.

The bird wants to reach the last tree while feeling tired as few times as possible. Other birds in the same forest want to reach the last tree with the same minimum amount of tiredness, and their values of $k$ can differ. For every bird, find the minimum number of times it feels tired.

The first line contains an integer $n$ ($2 \le n \le 1000000$), the number of trees.

The second line contains the integers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$). Here $d_i$ is the height of tree $i$.

The third line contains the number of birds $q$ ($1 \le q \le 25$) that want to fly to the last tree.

Line $i$ of the following $q$ lines contains $k_i$ ($1 \le k_i \le n-1$), the distance bird $i$ covers in one flight.

Print the answers on $q$ lines. Line $i$ contains the minimum number of times bird $i$ feels tired on its way to the last tree.

In the first example the bird with $k = 2$ visits trees 1, 3, 5, 7, 8, 9 in that order. It feels tired flying from tree 3 to tree 5 and from tree 7 to tree 8, so twice in total.