1119_D. Frets On Fire
Miyako came to the flea kingdom with a ukulele. She became good friends with local flea residents and played beautiful music for them every day.

In return, the fleas made a bigger ukulele for her: it has n strings, and each string has (10^{18} + 1) frets numerated from 0 to 10^{18}. The fleas use the array s_1, s_2, …, s_n to describe the ukulele's tuning, that is, the pitch of the j-th fret on the i-th string is the integer s_i + j.

Miyako is about to leave the kingdom, but the fleas hope that Miyako will answer some last questions for them.

Each question is in the form of: "How many different pitches are there, if we consider frets between l and r (inclusive) on all strings?"

Miyako is about to visit the cricket kingdom and has no time to answer all the questions. Please help her with this task!

Formally, you are given a matrix with n rows and (10^{18}+1) columns, where the cell in the i-th row and j-th column (0 ≤ j ≤ 10^{18}) contains the integer s_i + j. You are to answer q queries, in the k-th query you have to answer the number of distinct integers in the matrix from the l_k-th to the r_k-th columns, inclusive.

Input

The first line contains an integer n (1 ≤ n ≤ 100 000) — the number of strings.

The second line contains n integers s_1, s_2, …, s_n (0 ≤ s_i ≤ 10^{18}) — the tuning of the ukulele.

The third line contains an integer q (1 ≤ q ≤ 100 000) — the number of questions.

The k-th among the following q lines contains two integers l_k，r_k (0 ≤ l_k ≤ r_k ≤ 10^{18}) — a question from the fleas.

Output

Output one number for each question, separated by spaces — the number of different pitches.

Examples

Input

6
3 1 4 1 5 9
3
7 7
0 2
8 17


Output

5 10 18


Input

2
1 500000000000000000
2
1000000000000000000 1000000000000000000
0 1000000000000000000


Output

2 1500000000000000000

Note

For the first example, the pitches on the 6 strings are as follows.

$$$ \begin{matrix} Fret & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & … \\\ s_1: & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & ... \\\ s_2: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & ... \\\ s_3: & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & ... \\\ s_4: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & ... \\\ s_5: & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & ... \\\ s_6: & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & ... \end{matrix} $$$

There are 5 different pitches on fret 7 — 8, 10, 11, 12, 16.

There are 10 different pitches on frets 0, 1, 2 — 1, 2, 3, 4, 5, 6, 7, 9, 10, 11.
```python
import sys
import math
def lower(num,arr):
    ans=-1
    low,high=0,len(arr)-1
    while (low<=high):
        mid=(low+high)//2
        if arr[mid]<=num:
            ans=max(ans,mid)
            low=mid+1
        else:
            high=mid-1
    return ans
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))
arr.sort()
dif=[0 for _ in range(n-1)]
for i in range(1,n):
    dif[i-1]=arr[i]-arr[i-1]
dif.sort()
#print(dif,'dif')
if n!=1:
    pre=[dif[0]]
else:
    pre=[0]
for i in range(1,n-1):
    pre.append(pre[-1]+dif[i])
#print(pre,'pre')
q=int(sys.stdin.readline())
res=[]
for _ in range(q):
    l,r=map(int,sys.stdin.readline().split())
    x=(r-l+1)
    #print(x,'x')
    ind=lower(x,dif)
    #print(ind,'ind')
    y=pre[ind]
    if ind==-1:
        y=0
    #print(y,'y')
    z=n-1-(ind)
    #print(z,'z')
    ans=(z)*x+y
    res.append(ans)
print(*res)
    
    

```