AD đang bị đau chân sau một vụ tai nạn thảm khốc. Anh ấy không biết làm gì hơn ngoài việc ngồi chơi Tetris. Hôm đó em gái của AD chợt nghĩ ra một trò chơi đó là nhảy lò cò vượt chướng ngại vật, rất may mắn là vẫn còn một chân lành lặn nên anh ấy có thể tham gia. Trò chơi được chơi trên ~N~ bậc đánh số từ ~1~ đến ~N~, bậc thứ ~i~ có độ cao ~D_i~. Nhiệm vụ của người chơi là nhảy từ bậc ~1~ đến bậc ~N~. Mỗi người chơi có mức sức khỏe là ~K~ thì từ bậc ~i~ có thể nhảy đến các bậc ~i+1~, ~i+2~, ~\dots~, ~i+K~. Một bước nhảy từ bậc ~i~ đến bậc ~j~ được gọi là gây mất sức nếu như ~D_i \le D_j~. Em gái của AD rất tinh quái nên bắt anh phải tính ra số bước nhảy mất sức ít nhất để hoàn thành trò chơi rồi mới cho chơi! Không chỉ có thế, AD còn phải tính ra đáp án cho tất cả các bạn của em gái!

Input

• Dòng đầu chứa số ~N~
• Dòng thứ hai chứa ~N~ số ~D_i~
• Dòng thứ ba chứa ~Q~ là số lượng người AD phải giúp tính ra kết quả
• ~Q~ dòng tiếp theo mỗi dòng chứa một số ~K~ là mức sức khỏe của từng người

Output

~Q~ dòng mỗi dòng là kết quả đối với ~K~ tương ứng.

Giới hạn

• Trong tất cả các test: ~1 \le N \le 1000000~; ~1 \le D_i \le 10^9~; ~1 \le Q \le 25~; ~1 \le K < N~;
• Trong 20% số test đầu tiên: ~N \le 1000~;
• Trong 20% số test tiếp theo: ~N \le 100000~; ~D_i \le 10~;
• Trong 20% số test tiếp theo: ~N \le 100000~;
• Trong 20% số test tiếp theo: ~D_i \le 100~;
• Trong 20% số test còn lại: không có ràng buộc gì thêm.

Sample Input

10
3 10 5 3 1 3 2 6 3 4
2
2
3

Sample Output

3
2

Note

• Với ~K = 2~ có thể nhảy như nhau: 1~\rightarrow~2~\rightarrow~4~\rightarrow~6~\rightarrow~8~\rightarrow~10;
• Với ~K = 3~: 1~\rightarrow~2~\rightarrow~5~\rightarrow~8~\rightarrow~10;