시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 40 4 4 100.000%

문제

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

또한, 작은 새에게 지금 있는 나무보다 높은 나무로 올라가는 일은 낮은 나무로 내려가는 일보다 더 힘든 일이다. 작은 새는 자기가 현재 위치한 나무보다 같거나 높은 높이의 나무로 날아가면 피로감을 느낀다고 한다.

작은 새의 목표는 자신이 피로감을 느끼는 횟수를 최소화하면서 마지막 나무에 도달하는 것이다. 또한, 이 작은 새에게는 똑같이 최소한의 피로로 마지막 나무로 가고 싶어 하는 친구 새들이 있으며 이들의 k값은 서로 다를 수 있다. 작은 새와 친구 새들이 그들의 목표를 달성할 수 있도록 도와주자.

입력

첫 번째 줄에는 나무의 수를 나타내는 정수 n (2 ≤ n ≤ 1,000,000)이 주어진다.

다음 줄에는 n개의 정수 d1, d2, …, d(1 ≤ di ≤ 109) 가 주어진다. di는 i번째 나무의 높이를 의미한다.

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

다음 q개 줄 중 i번째 줄에는 i번째 새가 한 번의 비행으로 날아갈 수 있는 거리인 ki (1 ≤ ki ≤ n-1)가 주어진다.

출력

당신의 프로그램은 q줄에 걸쳐 답을 출력해야 한다. 출력의 i번째 줄에는 i번째 새가 마지막 나무에 도달할 때까지 피로감을 느끼는 횟수의 최소값을 출력해야 한다.

예제 입력

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

예제 출력

2
1

힌트

예제의 첫 번째 새는 1, 3, 5, 7, 8, 9번 나무를 거쳐 간다. 이 새는 3번째 나무에서 5번째 나무로 갈 때와 7번째 나무에서 8번째 나무로 갈 때, 총 두 번 피로감을 느낀다.