Dãy núi Alpha gồm ~N~ ngọn núi, được đánh số từ ~1~ đến ~N~ từ trái sang phải. Ngọn núi thứ ~i~ rộng ~1~ kilômét và cao ~H_i~ kilômét. Trên đỉnh mỗi ngọn núi có một ngôi làng.

Chính phủ đang chuẩn bị cho ~Q~ kịch bản có thể xảy ra. Trong kịch bản thứ ~i~, có ~W_i~ trận mưa rất lớn đổ xuống ngọn núi đầu tiên. Mỗi trận mưa tạo ra lượng nước đủ để nhấn chìm một ngôi làng dưới ~1~ kilômét nước.

Trong cùng một kịch bản, các trận mưa xảy ra lần lượt và lượng nước đã dừng lại sẽ nằm nguyên tại đó. Sau khi rơi xuống ngọn núi đầu tiên, mỗi đơn vị nước di chuyển theo các quy tắc sau:

• Nếu nước có thể chảy xuống dưới, nó sẽ chảy xuống.

• Nếu không, nếu nước có thể chảy sang phải, nó sẽ chảy sang phải.

• Nếu nước không thể chảy xuống dưới hoặc sang phải, nó sẽ dừng lại.

Nếu nước chảy sang phải ra khỏi ngọn núi thứ ~N~, các chuyển động tiếp theo của nó được bỏ qua.

Một ngôi làng được xem là bị ngập nếu có ít nhất một đơn vị nước đi qua nó, kể cả khi đơn vị nước đó không dừng lại ở ngôi làng này.

Trong mỗi kịch bản, chính phủ có ngân sách ~K~ đô la. Với ~1~ đô la, chính phủ có thể tăng chiều cao của một ngọn núi bất kỳ thêm ~1~ kilômét. Bằng cách sử dụng tối đa ~K~ đô la trước khi mưa bắt đầu, chính phủ muốn tối thiểu hóa số ngôi làng bị ngập.

Hãy tính số ngôi làng bị ngập ít nhất có thể trong từng kịch bản.

Lưu ý rằng các kịch bản là độc lập. Nói cách khác, trước mỗi kịch bản mới, chiều cao của tất cả ngọn núi trở lại giá trị ban đầu. Tuy nhiên, ngân sách ~K~ là như nhau trong mọi kịch bản.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(2 \le N \le 200000)~: số ngọn núi.

• Dòng thứ hai chứa ~N~ số nguyên ~H_1, H_2, \dots, H_N~ ~(1 \le H_i \le 1000000000)~: chiều cao các ngọn núi.

• Dòng thứ ba chứa hai số nguyên ~Q~ và ~K~ ~(1 \le Q \le 200000, 0 \le K \le 1000000000)~: số kịch bản và ngân sách.

• Dòng thứ tư chứa ~Q~ số nguyên ~W_1, W_2, \dots, W_Q~ ~(1 \le W_i \le 1000000000)~: số trận mưa trong từng kịch bản.

Output

In ra ~Q~ số nguyên trên một dòng, trong đó số thứ ~i~ là số ngôi làng bị ngập ít nhất có thể trong kịch bản thứ ~i~.

Scoring

Sample Input 1

6
4 2 1 5 2 4
6 2
1 2 6 12 15 25

Sample Output 1

2 3 3 3 5 6

Notes

Xét truy vấn thứ tư với ~W = 12~. Chính phủ tăng chiều cao ngọn núi ~4~ từ ~5~ lên ~7~, sử dụng đúng ~K = 2~ đô la. Khi đó cả ~12~ đơn vị nước đều bị giữ ở bên trái ngọn núi ~4~, nên chỉ các làng ~1, 2, 3~ bị nước đi qua và đáp án của truy vấn này là ~3~.

Với các giá trị ~W~ lần lượt là ~1, 2, 6, 12, 15, 25~, số làng bị ngập ít nhất tương ứng là ~2, 3, 3, 3, 5, 6~.