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, \ldots, 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 \le j \le 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 \leq n \leq 100\,000$) — the number of strings.

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

The third line contains an integer $q$ ($1 \leq q \leq 100\,000$) — the number of questions.

The $k$-th among the following $q$ lines contains two integers $l_k$，$r_k$ ($0 \leq l_k \leq r_k \leq 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} \textbf{Fret} & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \ldots \\ s_1: & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\ s_2: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_3: & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & \dots \\ s_4: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_5: & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \dots \\ s_6: & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & \dots \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$.

Difficulty: interview

Starter code:

Solutions:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return tuple(map(int, sys.stdin.readline().split()))
def LLI(): return [tuple(map(int, l.split())) for l in sys.stdin]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def main():
    n = I()
    a = sorted(LI())
    q = I()
    b = []
    for _ in range(q):
        l,r = LI()
        b.append(r-l+1)
    c = []
    for i in range(n-1):
        c.append(a[i+1]-a[i])
    c.sort()
    c.append(inf)

    d = sorted(b)
    e = {}
    s = 0
    t = n
    ci = 0
    for k in d:
        while c[ci] <= k:
            t -= 1
            s += c[ci]
            ci += 1
        e[k] = s + k * t

    rr = [e[k] for k in b]

    return ' '.join(map(str, rr))

print(main())




from bisect import bisect_left as bl
import sys
input = sys.stdin.readline
N = int(input())
A = sorted([int(a) for a in input().split()])
Q = int(input())

B = sorted([A[i+1] - A[i] for i in range(N-1)])
C = [0] * N
for i in range(1, N):
    C[i] = C[i-1] + B[i-1]
ANS = []
for q in range(Q):
    l, r = list(map(int, input().split()))
    k = r - l + 1
    i = bl(B, k)
    ANS.append(k * (N - i) + C[i])

print(*ANS)


from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))


n=nn()

strings=lm()

q=nn()


strings.sort()

diffs=[]

for i in range(1,n):
	diffs.append(strings[i]-strings[i-1])

diffs.sort(reverse=True)

if not n==1:

	runninggaps=[diffs[0]]


for i in range(1,n-1):
	runninggaps.append(runninggaps[-1]+diffs[i])



answers=[]


for i in range(q):
	
	

	l,r=mi()

	if n==1:
		answers.append(r-l+1)		
		continue

	gap=r-l+1

	maxrange=strings[-1]-strings[0]+gap	
	start=0

	end=n-2
	#print(maxrange,diffs)
	while start<=end:

		mid=(start+end)//2

		if diffs[mid]>gap:
			start=mid+1

		else:
			end=mid-1

	#print(end)

	if end==-1:
		pass
	else:
		maxrange+= gap*(end+1)-runninggaps[end]
	
	answers.append(maxrange)

print(*answers)











import sys
import bisect

n = int(input())

s = sorted([int(x) for x in input().split(' ')])
dif = sorted([(s[i + 1] - s[i]) for i in range(0, n - 1)])
adif = []
if n > 1:
    adif.append(dif[0])
    for i in range(1, len(dif)):
        adif.append(adif[-1] + dif[i])

q = int(input())
res = []
for i in range(q):
    line = input().split(' ')
    l = int(line[0])
    r = int(line[1])
    span = r - l + 1
    idx = bisect.bisect_right(dif, span) - 1
    if idx >= 0:
        acc_diff = adif[idx]
        ans = n * span - ((idx + 1) * span - acc_diff)
    else:
        ans = n * span

    res.append(ans)

print(str(" ".join(str(x) for x in res)))

n=int(input())
answer=[]
summa={}
summa[0]=0
def bin(p):
    left=0
    right=lena
    while right-left>1:
        mid=(left+right)//2
        if res[mid]<=p:
            left=mid
        else:
            right=mid
    return left+1
uku=list(set([int(x) for x in input().split()]))
uku.sort()
res=[]
for i in range(1,len(uku)):
    res.append(uku[i]-uku[i-1])
q=int(input())
res.append(10**100)
res.sort()
counter=0
i=1
for item in res:
    counter+=item
    summa[i]=counter
    i+=1
lena=len(res)
for i in range(q):
    l,r=[int(x) for x in input().split()]
    s=r-l+1
    counter=0
    if s<res[0]:
        bina=0
    else:
        bina=bin(s)
    counter=summa[bina]+s*(lena-bina)
    
    answer.append(counter)
print(*answer)


import sys

n = int(sys.stdin.readline().strip())
ans = []
s = list(map(int, sys.stdin.readline().strip().split()))
s.sort()
t = [0] * n
c = [0] * (n + 1)
for i in range (0, n - 1):
    t[i] = s[i + 1] - s[i]
t[n - 1] = 10 ** 18 + 1
t.sort()
for i in range (0, n):
    c[i + 1] = c[i] + t[i]
q = int(sys.stdin.readline().strip())
for i in range (0, q):
    line = sys.stdin.readline().strip().split()
    l = int(line[1]) - int(line[0]) + 1
    j1 = 0
    j2 = n
    j = (j1 + j2) // 2
    if t[0] > l:
        j1 = -1
    else:
        while j2 - j1 > 1:
            if t[j] <= l:
                j1 = j
            else:
                j2 = j
            j = (j1 + j2) // 2
    ans.append(str((c[j1 + 1] + (n - j1 - 1) * l)))
print(" ".join(ans))

def main():
    from bisect import bisect
    from itertools import accumulate, chain
    from sys import stdin, stdout

    input = stdin.readline
    input()
    s = sorted(set(map(int, input().split())))
    n = len(s)
    inp = sorted((a - b for (a, b) in zip(s[1:], s)))
    acc = tuple(chain(accumulate(inp), (0,)))
    for _ in range(int(input())):
        l_, r = list(map(int, input().split()))
        d = r + 1 - l_
        i = bisect(inp, d)
        stdout.write(f'{acc[i - 1] + (n - i) * d} ')


main()


import bisect
n=int(input())
s=[*map(int, input().split())]
s.sort()
t=[a-b for a,b in zip(s[1:],s)]+[100000000000000000000]
t.sort()
S=[0]
for i in range(n):S+=[S[-1]+t[i]]
R=[]
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    L=r-l+1
    j=bisect.bisect_left(t,L)
    R+=[S[j]+(n-j)*L]
print(' '.join(map(str,R)))

from bisect import bisect
from collections import Counter

n = int(input())
ns_ = sorted(map(int, input().split()))
diffs = [(b - a) for a, b in zip(ns_, ns_[1:])]
ns = set(ns_)

cnt = Counter(diffs)
cnt.pop(0, None)
sck = sorted(cnt.keys())
remain = [len(ns)]
for k in sck:
    remain.append(remain[-1] - cnt[k])

lastat = [0, *sck]

ans = [remain[0]]
for i in range(len(cnt)):
    ans.append(ans[-1] + remain[i + 1] + remain[i] * (lastat[i + 1] - lastat[i] - 1))

q = int(input())
out = []
for _ in range(q):
    ll, r = list(map(int, input().split()))
    x = r - ll
    at = bisect(lastat, x) - 1
    out.append(ans[at] + remain[at] * (x - lastat[at]))

print(' '.join(map(str, out)))


#!/usr/bin/env python


from bisect import bisect_left


def main():
    n = int(input())
    s = sorted(int(si) for si in input().split())

    ediff = sorted(x - s[i - 1] for i, x in enumerate(s) if i > 0)

    cumsum = [0] * n
    for i in range(n - 1):
        cumsum[i + 1] = cumsum[i] + ediff[i]

    q = int(input())
    for _ in range(q):
        l, r = list(map(int, input().split()))
        ind = bisect_left(ediff, r - l + 1)
        print((r - l + 1) * (n - ind) + cumsum[ind], end=' ')


def __starting_point():
    main()

__starting_point()

from bisect import bisect_left

n = int(input())
s = sorted(int(si) for si in input().split())
ediff = sorted(x - s[i - 1] for i, x in enumerate(s) if i > 0)

cumsum = [0] * n
for i in range(n - 1):
    cumsum[i + 1] = cumsum[i] + ediff[i]

for _ in range(int(input())):
    l, r = map(int, input().split())
    ind = bisect_left(ediff, r - l + 1)
    print((r - l + 1) * (n - ind) + cumsum[ind], end=' ')


import math
def f5(seq, idfun=None):
   # order preserving
   if idfun is None:
       def idfun(x): return x
   seen = {}
   result = []
   for item in seq:
       marker = idfun(item)
       if marker in seen: continue
       seen[marker] = 1
       result.append(item)
   return result

def upper_bound(v, val):
    l = 0
    r = len(v)
    while l+1<r :
        mid = (l+r)//2
        if v[mid] <= val:
            l=mid
        else:
            r=mid
    return r

N = list(map(int,input().split()))
inp = [*list(map(int, input().split()))]
inp = sorted(f5(inp))
N = len(inp)
mp = {}
v = []
i = 0
while i < N-1:
    gap = inp[i+1]-inp[i]
    v.append(gap)
    mp[gap] = 0
    i = i + 1
for gap in v:
    mp[gap] = mp[gap] + 1
v.append(0)
v = sorted(f5(v))
psum1 = [0] * (len(mp) + 1)
psum0 = [0] * (len(mp) + 1)

i = 1
while i <= len(mp):
    cur = v[i]
    psum1[i] = psum1[i-1] + (psum0[i-1]*(cur-v[i-1])) + mp[cur]
    psum0[i] = psum0[i-1] + mp[cur]
    i = i+1
Q = int(input())
ansstring = ''
while Q>0:
    l, r = list(map(int,input().split()))
    siz = r-l
    idx = upper_bound(v,siz)-1
    ans = N * (siz + 1)
    remain = siz-v[idx]
    ans -= psum1[idx]
    ans -= psum0[idx] * remain
    ansstring += str(ans) + ' '
    Q = Q-1
print(ansstring)


import copy
import bisect

n = int(input())
s = list(map(int, input().split()))
sCopy = copy.deepcopy(s)

AP = []
mx = -1
sCopy.sort()
miss = []
for i in range(n-1):
    mx = max(mx, sCopy[i+1]-sCopy[i]-1, 0)
    miss.append(max(sCopy[i+1]-sCopy[i]-1, 0))

miss.sort()
if miss!=[]:
    pSOfMiss = [miss[0]]
    for i in range(1, len(miss)):
        pSOfMiss.append(pSOfMiss[-1]+miss[i])

MAX = max(s)
MIN = min(s)
C = len(set(s))
ansList = []
#print(miss, mx)
#print(pSOfMiss)
mL = len(miss)
q = int(input())
for _ in range(q):
    l, r = list(map(int, input().split()))
    if l==r:
        ansList.append(C)
    elif n==1:
        ans = r-l+1
        ansList.append(ans)
    elif r-l>=mx:
        ans = (MAX+r)-(MIN+l)+1
        ansList.append(ans)
    else:
        idx = bisect.bisect_right(miss, r-l)
        if idx>0:
            notThere = pSOfMiss[-1]-pSOfMiss[idx-1]-((r-l)*(mL-idx))
        else:
            notThere = pSOfMiss[-1] - ((r-l)*(mL-idx))
        #print(l, r, notThere, idx)
        ans = (MAX+r)-(MIN+l)+1-notThere
        ansList.append(ans)

print(*ansList)


from bisect import bisect_left as j
k,w,b=input,int,sorted;f=lambda:map(w,k().split());n=w(k());s=b([*f()]);e,c = b(x-s[i-1]for i,x in enumerate(s)if i>0),[0]*n
for i in range(n-1):c[i+1]=c[i]+e[i]
for _ in range(w(k())):l,r=f();i=j(e,r-l+1);print((r-l+1)*(n-i)+c[i],end=' ')

import sys
input = sys.stdin.readline
stdout = sys.stdout
rr = lambda: input().strip()
rri = lambda: int(rr())
rrm = lambda: list(map(int, rr().split()))

from bisect import bisect

N = rri()
A = rrm()
Q = rri()
A.sort()
D = sorted(A[i+1] - A[i] for i in range(N-1))
P = [0]
for x in D:
    P.append(P[-1] + x)

queries = []
for q in range(Q):
    L, R = rrm()
    queries.append((R-L+1, q))
queries.sort()
ans = [None] * len(queries)

i = 0
for q, ix in queries:
    bns = q
    # bns += sum(min(d, w) for d in D)
    i = bisect(D, q, i)
    bns += P[i] + q * (len(D) - i)
    ans[ix] = bns

print(*ans)


import sys
input = sys.stdin.readline
stdout = sys.stdout
rr = lambda: input().strip()
rri = lambda: int(input())
rrm = lambda: list(map(int, input().strip().split()))

from bisect import bisect

N = rri()
A = rrm()
Q = rri()
A.sort()
D = sorted(A[i+1] - A[i] for i in range(N-1))
P = [0]
for x in D:
    P.append(P[-1] + x)

queries = []
for q in range(Q):
    L, R = rrm()
    queries.append((R-L+1, q))
queries.sort()
ans = [None] * len(queries)

i = 0
for q, ix in queries:
    bns = q
    # bns += sum(min(d, w) for d in D)
    i = bisect(D, q, i)
    bns += P[i] + q * (len(D) - i)
    ans[ix] = bns

print(*ans)