409762: GYM103736 C Check Problems

Now, $$$n$$$ people are checking the problems. There are $$$10^{10^{10}}$$$ problems in total and numbered from $$$1$$$ to $$$10^{10^{10}}$$$. The $$$i$$$-th person starts the check from the $$$a_i$$$ problem. It takes one minute to check a problem. More formally, the problem with the number $$$a_i+j-1$$$ will be checked by the $$$i$$$-th person at the $$$j$$$-th minute.

Now, your task is to answer $$$q$$$ queries. Each query will give you an integer $$$t$$$, please calculate the number of problems that have been tested at least once after $$$t$$$ minutes.

The first line contains a single integer $$$n (1 \leq n \leq 5 \cdot 10^5)$$$ indicating the number of people.

The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots,a_n$$$ $$$(1 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq 10^{18})$$$ indicating the problem number of the first check for the $$$i$$$-th person.

The next line contains a single integer $$$q$$$ $$$(1 \leq q \leq 5 \cdot 10^5)$$$ indicating the number of queries.

Each of the next $$$q$$$ lines contains an integer $$$t$$$ $$$(0 \leq t \leq 10^{18})$$$.

it is guaranteed that $$$a_{i+1}-a_i \leq a_{i+2}-a_{i+1}$$$ for every $$$1 \leq i \leq n - 2$$$.

For each query, output the total number of problems that have been tested at least once after $$$t$$$ minutes in one line.

3
1 3 8
3
2
4
10

6
10
17

After two minutes, the first person checked $$$[1,2]$$$ problems, the second person checked $$$[3,4]$$$ problems and the third person checked $$$[8,9]$$$ problems, the answer is $$$6$$$.

After four minutes, the first person checked $$$[1,2,3,4]$$$, the second person checked $$$[3,4,5,6]$$$, and the third person checked $$$[8,9,10,11]$$$, the answer is $$$10$$$.