All that jazz

Stavroula really likes jazz music. She won the lottery, so she decides to take a trip to New Orleans and attend as many jazz concerts as possible. Help her plan her trip!

In the near future, ~N~ jazz concerts will be held in New Orleans, and for each concert, the date ~D_i~ on which it will take place is known. For simplicity reasons, in this problem, we have replaced the dates with positive integers: day ~1~, day ~2~, and so on.

Stavroula hasn't decided yet when she will go or how many days she will stay in New Orleans. She wants your help in deciding, by answering a total of ~Q~ queries, each of the form: "If I go for ~K_i~ days to New Orleans and plan my departure optimally, how many concerts can I attend?"

Consider that Stavroula will be able to attend all concerts taking place during her entire stay in New Orleans, including the first and last days. Also, she can attend more than one concert on the same day.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the information about the concerts and Stavroula's queries and provides the answers.

Input Files:

The input files named allthatjazz.in are text files with the following structure: The first line contains a positive integer ~N~: the number of concerts. The second line contains exactly ~N~ integers ~D_i~ (where ~1 \le i \le N~), separated in pairs by a single space: the day each of the ~N~ concerts is held. The third line contains a positive integer: the number of questions ~Q~. The fourth line contains exactly ~Q~ integers ~K_i~ (where ~1 \le i \le Q~), separated in pairs by a single space: the duration in days of Stavroula's trip for the ~i~-th question.

Output Files:

The output files named allthatjazz.out are text files with the following structure. They must contain exactly ~Q~ lines, where each line contains exactly one integer: the answer to the ~i~-th question, in order.

Constraints:

• 1 ~\le N \le~ 1.000.000, 1 ~\le Q \le~ 1.000.000 and ~N \times Q \le~ 2.000.000
• 1 ~\le D_i \le~ 1.000.000.000 for each ~i~, where 1 ~\le i \le~ ~N~
• 1 ~\le K_i \le~ 1.000.000.000 for each ~i~, where 1 ~\le i \le~ ~Q~

Examples of Input - Output Files:

STDIN (allthatjazz.in)

6
7 4 2 5 4 3
7
3 4 2 1 6 2 5

STDOUT (allthatjazz.out)

4
5
3
2
6
3
5

Explanation of the example:

There will be a total of ~N=6~ concerts. The first one will be on day ~7~, the second on day ~4~, the third on day ~2~, and so on. Note that on day ~4~, two concerts will take place. Also, on some days, for example, on day ~1~ and day ~6~, no concerts will be held.

We need to answer ~Q=7~ questions:

• For ~K=3~, meaning if Stavroula stays for ~3~ days in New Orleans, how many concerts can she attend at most? If she arrives on day ~2~ and stays until day ~4~ (a total of ~3~ days), she can attend a maximum of ~4~ concerts: one on day ~2~, one on day ~3~, and two on day ~4~. This is the maximum she can achieve for a stay of ~3~ days.
• For ~K=4~, from day ~2~ to day ~5~, a total of ~5~ concerts.
• For ~K=2~, from day ~3~ to day ~4~, a total of ~3~ concerts.
• For ~K=1~, only on day ~4~, a total of ~2~ concerts.
• For ~K=6~, from day ~2~ to day ~7~, a total of ~6~ concerts.
• For ~K=2~, the same question has already been answered.
• For ~K=5~, from day ~1~ to day ~5~, a total of ~5~ concerts.

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: allthatjazz *)

for PASCAL coders

/* USER: username
LANG: C
TASK: allthatjazz */

for C coders

/* USER: username
LANG: C++
TASK: allthatjazz */

for C++ coders

/* USER: username
LANG: Java
TASK: allthatjazz */

for Java coders

# USER: username
# LANG: Python
# TASK: allthatjazz

for Python coders