작은 새

경기과학고 뒤뜰에는 나무 $n$그루가 일렬로 선 숲이 있다. 첫 번째 나무 위에는 마지막 나무 위로 올라가고 싶어 하는 작은 새가 한 마리 있다. 이 새는 몸집이 아주 작아서 한 번의 비행으로 날아갈 수 있는 거리에 한계가 있다. 새가 $i$번째 나무 위에 있으면 한 번의 비행으로 $i+1, i+2, \dots, i+k$번째 나무 중 하나로 갈 수 있고, 그보다 멀리 떨어진 나무로는 가지 못한다.

작은 새에게 지금 있는 나무보다 높은 나무로 올라가는 일은 낮은 나무로 내려가는 일보다 더 힘들다. 새는 자기가 앉아 있는 나무와 높이가 같거나 더 높은 나무로 날아가면 피로감을 느낀다.

작은 새의 목표는 피로감을 느끼는 횟수를 최소로 하면서 마지막 나무에 도달하는 것이다. 같은 숲에는 똑같이 최소한의 피로로 마지막 나무까지 가고 싶어 하는 친구 새도 있으며, 새마다 $k$ 값이 다를 수 있다. 새마다 피로감을 느끼는 횟수의 최솟값을 구하라.

첫째 줄에 나무의 수를 나타내는 정수 $n$ ($2 \le n \le 1000000$)이 주어진다.

둘째 줄에 정수 $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$)이 주어진다. $d_i$는 $i$번째 나무의 높이다.

셋째 줄에 마지막 나무로 날아가고 싶어 하는 새의 수 $q$ ($1 \le q \le 25$)가 주어진다.

이어지는 $q$개 줄 중 $i$번째 줄에는 $i$번째 새가 한 번의 비행으로 날아갈 수 있는 거리 $k_i$ ($1 \le k_i \le n-1$)가 주어진다.

$q$개 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번째 새가 마지막 나무에 도달할 때까지 피로감을 느끼는 횟수의 최솟값을 출력한다.

첫 번째 예제에서 $k = 2$인 새는 1, 3, 5, 7, 8, 9번 나무를 차례로 거쳐 간다. 이 새는 3번 나무에서 5번 나무로 갈 때와 7번 나무에서 8번 나무로 갈 때 피로감을 느끼므로, 모두 두 번 느낀다.