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: MEDIUM_HARD
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
import sys
input = sys.stdin.readline
n = int(input())
s = list(map(int, input().split()))
s.sort()
q = int(input())
qrs = []
for i in range(q):
	(l, r) = map(int, input().split())
	qrs.append((r - l, i))
qrs.sort()
stoppers = sorted([s[i] - s[i - 1] for i in range(1, len(s))])
stopper_sum = 0
stopper_cnt = 0
si = 0
answers = []
for (x, i) in qrs:
	while si < len(stoppers) and stoppers[si] <= x:
		stopper_cnt += 1
		stopper_sum += stoppers[si]
		si += 1
	answers.append((i, (x + 1) * (len(s) - stopper_cnt) + stopper_sum))
answers.sort()
sys.stdout.write(' '.join((str(x[1]) for x in answers)))


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
	i = bisect(D, q, i)
	bns += P[i] + q * (len(D) - i)
	ans[ix] = bns
print(*ans)


n = int(input())
s = list(map(int, input().split()))
if n == 1:
	q = int(input())
	out = [0] * q
	for u in range(q):
		(a, b) = map(int, input().split())
		out[u] = str(b - a + 1)
	print(' '.join(out))
	exit()
s.sort()
diffs = [s[i + 1] - s[i] for i in range(n - 1)]
diffs.sort()
parts = [0] * (n - 1)
parts[0] = diffs[0] * n
for i in range(n - 2):
	parts[i + 1] = parts[i] + (diffs[i + 1] - diffs[i]) * (n - i - 1)
q = int(input())
out = [0] * q
for u in range(q):
	(a, b) = map(int, input().split())
	size = b - a + 1
	if size <= diffs[0]:
		out[u] = n * size
	elif size >= diffs[-1]:
		out[u] = parts[-1] + size - diffs[-1]
	else:
		big = n - 2
		sml = 0
		curr = (n - 2) // 2
		while big - sml > 1:
			if size > diffs[curr]:
				sml = curr
				curr = (big + sml) // 2
			elif size < diffs[curr]:
				big = curr
				curr = (big + sml) // 2
			else:
				big = sml = curr
		if big == sml:
			out[u] = parts[big]
		else:
			rat = (parts[big] - parts[sml]) // (diffs[big] - diffs[sml])
			out[u] = parts[sml] + rat * (size - diffs[sml])
out = [str(guy) for guy in out]
print(' '.join(out))


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) = 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)))


from sys import stdin, stdout
import bisect
n = int(input())
a = list(map(int, stdin.readline().split()))
a = sorted(a)
if n == 1:
	q = int(input())
	out = []
	while q > 0:
		(l, r) = map(int, stdin.readline().split())
		txt = str(r - l + 1)
		out.append(txt)
		q -= 1
	stdout.write(' '.join(out))
else:
	d = [0 for i in range(n - 1)]
	for i in range(1, n):
		d[i - 1] = a[i] - a[i - 1]
	d = sorted(d)
	s = [0 for i in range(n - 1)]
	s[0] = d[0]
	for i in range(1, n - 1):
		s[i] = s[i - 1] + d[i]
	q = int(input())
	out = []
	while q > 0:
		(l, r) = map(int, stdin.readline().split())
		tot = r - l + 1
		ans = tot * n
		p = bisect.bisect_right(d, tot) - 1
		if p >= 0:
			ans -= tot * (p + 1) - s[p]
		out.append(str(ans))
		q -= 1
	stdout.write(' '.join(out))


from bisect import bisect_right
import sys
input = sys.stdin.readline
n = int(input())
s = [int(x) for x in input().split()]
d = []
s.sort()
for i in range(n - 1):
	d.append(s[i + 1] - s[i])
d.sort()
if n > 1:
	pre = [d[0]]
	for i in range(n - 2):
		pre.append(pre[i] + d[i + 1])
q = int(input())
for _ in range(q):
	[l, r] = [int(x) for x in input().split()]
	(l, r) = (0, r - l)
	if n == 1:
		print(r + 1, end=' ')
	elif d[0] > r + 1:
		print((r + 1) * n, end=' ')
	else:
		l = bisect_right(d, r + 1)
		l = l - 1
		print(pre[l] + (r + 1) * (n - l - 1), end=' ')


from bisect import bisect
n = int(input())
arr = sorted(set(map(int, input().split())))
diff = sorted(map(lambda x, y: x - y, arr[1:], arr))
uniq = [0] * (len(diff) + 1)
for i in range(1, len(uniq)):
	uniq[i] = uniq[i - 1] + diff[i - 1]
for _ in range(int(input())):
	(l, r) = list(map(int, input().split()))
	rang = r - l + 1
	pos = bisect(diff, rang)
	print(uniq[pos] + (len(arr) - pos) * rang, end=' ')


import sys
input = sys.stdin.readline

def bs(num):
	low = 0
	high = len(diff) - 1
	while low < high:
		mid = (low + high) // 2
		if diff[mid] <= num:
			low = mid + 1
		else:
			high = mid - 1
	if diff[low] <= num:
		return len(diff) - low - 1
	else:
		return len(diff) - low
int(input())
s = sorted(list(set(map(int, input().split()))))
n = len(s)
diff = []
for i in range(1, n):
	diff.append(s[i] - s[i - 1])
diff.sort()
if n == 1:
	for i in range(int(input())):
		(l, r) = map(int, input().split())
		print(r - l + 1, end=' ')
	exit()
suff = [diff[-1]]
for i in range(len(diff) - 2, -1, -1):
	suff.append(suff[-1] + diff[i])
(minn, maxx) = (min(s), max(s))
for i in range(int(input())):
	(l, r) = map(int, input().split())
	count = bs(r - l + 1)
	if count == 0:
		print(maxx + r - minn - l + 1, end=' ')
	else:
		print(maxx + r - minn - l + 1 - (suff[count - 1] - count * (r - l + 1)), end=' ')
print()


import sys
input = sys.stdin.readline
n = int(input())
s = [int(x) for x in input().split()]
d = []
s.sort()
for i in range(n - 1):
	d.append(s[i + 1] - s[i])
d.sort()
if n > 1:
	pre = [d[0]]
	for i in range(n - 2):
		pre.append(pre[i] + d[i + 1])
q = int(input())
for _ in range(q):
	[l, r] = [int(x) for x in input().split()]
	(l, r) = (0, r - l)
	if n == 1:
		print(r + 1, end=' ')
	elif d[0] > r + 1:
		print((r + 1) * n, end=' ')
	else:
		lo = 0
		hi = n - 2
		while lo < hi:
			mi = (lo + hi + 1) // 2
			if d[mi] <= r + 1:
				lo = mi
			else:
				hi = mi - 1
		print(pre[lo] + (r + 1) * (n - lo - 1), end=' ')


import bisect
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a = set(a)
a = list(a)
n = len(a)
a.sort()
h = []
for i in range(n - 1):
	if a[i + 1] - a[i] > 1:
		h.append(a[i + 1] - a[i] - 1)
m = len(h)
h.sort()
rui = [0] * (m + 1)
for i in range(m):
	rui[i + 1] = rui[i] + h[i]
q = int(input())
ans = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
	(aa, bb) = ans[i]
	c = bb - aa
	d = bisect.bisect_left(h, c)
	print(rui[d] + c * (m - d) + n + c)


from sys import stdin
from bisect import bisect_right as bl
n = int(stdin.readline().strip())
s = list(set(map(int, stdin.readline().strip().split())))
s.sort()
n = len(s)
dist = []
for i in range(1, n):
	dist.append(s[i] - s[i - 1])
if len(dist) == 0:
	dist = [0]
dist.sort()
arr = [0]
arr2 = [len(s)]
x = len(s)
y = len(s)
for i in range(1, len(dist)):
	x -= 1
	if dist[i] != dist[i - 1]:
		arr.append(dist[i - 1])
		arr2.append(x)
arr.append(dist[-1])
arr2.append(1)
acum = [n]
for i in range(1, len(arr2)):
	acum.append(acum[i - 1] + (arr[i] - arr[i - 1] - 1) * arr2[i - 1] + arr2[i])
ans = []
q = int(stdin.readline().strip())
for i in range(q):
	(l, r) = map(int, stdin.readline().strip().split())
	d = r - l
	ind = bl(arr, d) - 1
	ans.append(acum[ind] + (d - arr[ind]) * arr2[ind])
print(*ans)


import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
a.append(10 ** 40)
q = int(input())
a.sort()
collect = []
for i in range(1, n + 1):
	if a[i] - a[i - 1] - 1 >= 0:
		collect.append(a[i] - a[i - 1] - 1)
count = len(collect)
collect.sort()
sum_collect = [0]
add = 0
for i in range(count):
	add += collect[i]
	sum_collect.append(add)
collect = [0] + collect
ans = []
for _ in range(q):
	(l, r) = map(int, input().split())
	d = r - l
	ll = 0
	rr = count
	while ll < rr:
		m = (ll + rr) // 2
		if collect[m] > d:
			rr = m - 1
		else:
			ll = m + 1
	if collect[ll] > d:
		ll -= 1
	ans.append(count + sum_collect[ll] + (count - ll) * d)
print(*ans)


import os, sys
from io import BytesIO

class FastI:
	stream = BytesIO()
	newlines = 0

	def readline(self):
		while self.newlines == 0:
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			(self.stream.seek(0, 2), self.stream.write(b), self.stream.seek(ptr))
			self.newlines += b.count(b'\n') + (not b)
		self.newlines -= 1
		return self.stream.readline()

class FastO:

	def __init__(self):
		stream = BytesIO()
		self.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
		self.write = lambda b: stream.write(b.encode())

class ostream:

	def __lshift__(self, a):
		if a == endl:
			sys.stdout.write('\n')
			sys.stdout.flush()
		else:
			sys.stdout.write(str(a))
		return self
(sys.stdin, sys.stdout) = (FastI(), FastO())
(input, flush) = (sys.stdin.readline, sys.stdout.flush)
(cout, endl) = (ostream(), object())
rr = lambda : input().strip()
rri = lambda : int(input())
rrm = lambda : list(map(int, input().strip().split()))

def main():
	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
		i = bisect(D, q, i)
		bns += P[i] + q * (len(D) - i)
		ans[ix] = bns
	print(*ans)
main()


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))))


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))


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	diff = [0]
	arr.sort()
	for i in range(1, n):
		diff.append(arr[i] - arr[i - 1])
	diff.sort()
	pre = [diff[0]]
	for i in range(1, n):
		pre.append(pre[-1] + diff[i])
	final = []
	for i in range(int(input())):
		(l, r) = list(map(int, input().split()))
		x = r - l + 1
		lo = 0
		hi = n - 1
		if diff[-1] <= x:
			final.append(pre[-1] + x)
		elif diff[0] >= x:
			final.append(n * x)
		else:
			while lo < hi:
				m = (lo + hi) // 2
				if diff[m] < x:
					lo = m
				else:
					hi = m
				if hi - lo == 1:
					break
			if diff[lo] >= x:
				final.append(pre[lo - 1] + x * (n - lo) + min(diff[lo], x))
			else:
				final.append(pre[hi - 1] + x * (n - hi) + min(diff[hi], x))
	print(*final)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from bisect import bisect_left, bisect_right
n = int(input())
s = [int(i) for i in input().split(' ')]
s = sorted(s)
diff = []
for i in range(1, n):
	diff.append(s[i] - s[i - 1])
diff = sorted(diff)
prefix_sum = [0]
temp = n
pre = 0
for i in diff:
	prefix_sum.append(prefix_sum[-1] + temp * (i - pre))
	pre = i
	temp -= 1

def query(arr, prefix, v):
	i = bisect_right(arr, v)
	if i == 0:
		return n * (v + 1)
	return prefix[i] + (v - arr[i - 1] + 1) * (n - i)
q = int(input())
for i in range(q):
	(l, r) = [int(i) for i in input().split(' ')]
	print(query(diff, prefix_sum, r - l))


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 = []
mL = len(miss)
q = int(input())
for _ in range(q):
	(l, r) = 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)
		ans = MAX + r - (MIN + l) + 1 - notThere
		ansList.append(ans)
print(*ansList)


import bisect
import sys
input = sys.stdin.readline
n = int(input())
l = input().split()
li = [int(i) for i in l]
li.sort()
diff = []
for i in range(n - 1):
	diff.append(li[i + 1] - li[i])
diff.sort()
pref = [0 for i in range(n - 1)]
sumi = 0
for i in range(n - 1):
	sumi = sumi + diff[i]
	pref[i] = sumi
q = int(input())
for i in range(q):
	l = input().split()
	r = int(l[1])
	l = int(l[0])
	z = r - l + 1
	k = bisect.bisect_right(diff, z)
	ans = 0
	if k > 0:
		ans += pref[k - 1]
	ans += (n - 1 - k) * z
	ans += z
	print(ans)


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()
if n != 1:
	pre = [dif[0]]
else:
	pre = [0]
for i in range(1, n - 1):
	pre.append(pre[-1] + dif[i])
q = int(sys.stdin.readline())
res = []
for _ in range(q):
	(l, r) = map(int, sys.stdin.readline().split())
	x = r - l + 1
	ind = lower(x, dif)
	y = pre[ind]
	if ind == -1:
		y = 0
	z = n - 1 - ind
	ans = z * x + y
	res.append(ans)
print(*res)


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=' ')


from sys import stdin
from bisect import *
input = stdin.readline
n = int(input())
s = list(map(int, input().split()))
s.sort()
dif = [s[i + 1] - s[i] for i in range(n - 1)]
dif.sort()
pref = [0]
for i in range(len(dif)):
	pref.append(pref[-1] + dif[i])
for i in range(int(input())):
	(l, r) = map(int, input().split())
	x = r - l + 1
	r = len(dif)
	l = 0
	while l < r:
		m = (l + r) // 2
		if dif[m] < x:
			l = m + 1
		else:
			r = m
	ans = x * (n - l) + pref[l]
	print(ans, end=' ')


from bisect import bisect
n = int(input())
a = sorted(set(map(int, input().split())))
dd = sorted(map(lambda x, y: x - y, a[1:], a))
ddd = [0]
for v in dd:
	ddd.append(ddd[-1] + v)
s = len(a)
k = int(input())
for j in range(k):
	(l, r) = map(int, input().split())
	d = r - l + 1
	i = bisect(dd, d)
	print(' ' if j else '', ddd[i] + (s - i) * d, end='')
print()


from bisect import bisect_left
T = int(input())
ls = sorted(list(set(map(int, input().split()))))
M = len(ls)
d = {}
for i in range(len(ls) - 1):
	d[ls[i]] = ls[i + 1] - ls[i]
ls = sorted(list(d.values()))
N = len(ls)
prev = [0]
for i in ls:
	prev.append(prev[-1] + i)
Q = int(input())
for i in range(Q):
	(x, y) = map(int, input().split())
	c = bisect_left(ls, y - x + 1)
	print(prev[c] + (M - c) * (y - x + 1), end=' ')
print()


import sys
input = sys.stdin.readline
from bisect import *
n = int(input())
s = list(map(int, input().split()))
s.sort()
d = [s[i + 1] - s[i] for i in range(n - 1)]
d.sort()
d_acc = [0]
for di in d:
	d_acc.append(d_acc[-1] + di)
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	mark = bisect_right(d, r - l + 1)
	sub = d_acc[n - 1] - d_acc[mark] - (n - mark - 1) * (r - l + 1)
	ans = s[-1] + r - (s[0] + l) + 1 - sub
	if i < q - 1:
		print(ans, end=' ')
	else:
		print(ans)


import math

def f5(seq, idfun=None):
	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 os
import sys
from io import BytesIO, IOBase
from collections import Counter
import string
import heapq
import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

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

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def get_str():
	return input().strip()

def get_strs():
	return input().strip().split(' ')

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a, drop_zero=False):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	if drop_zero:
		return p[1:]
	else:
		return p

def prefix_mins(a, drop_zero=False):
	p = [float('inf')]
	for x in a:
		p.append(min(p[-1], x))
	if drop_zero:
		return p[1:]
	else:
		return p

def solve():
	n = get_int()
	s = get_ints()
	s.sort()
	d = []
	for i in range(1, n):
		d.append(s[i] - s[i - 1])
	d.append(float('inf'))
	d_cnt = [(k, v) for (k, v) in Counter(d).items()]
	d_cnt.sort()
	d_idxs = [d for (d, cnt) in d_cnt]
	d_prods = [d * cnt for (d, cnt) in d_cnt]
	d_cnts = [cnt for (d, cnt) in d_cnt]
	d_prods_pref = prefix_sums(d_prods)
	d_cnts_pref = prefix_sums(d_cnts)
	q = get_int()

	def query():
		(l, r) = get_ints()
		w = r - l + 1
		idx = bisect.bisect_left(d_idxs, w)
		return d_prods_pref[idx] + w * (n - d_cnts_pref[idx])
	return [query() for i in range(q)]
print(*solve())


from __future__ import division, print_function
import os
import sys
from bisect import bisect_left
from io import IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from cStringIO import StringIO
	from future_builtins import ascii, filter, hex, map, oct, zip
else:
	from io import BytesIO as StringIO

class FastI:
	stream = StringIO()
	newlines = 0

	def readline(self):
		while self.newlines == 0:
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			(self.stream.seek(0, 2), self.stream.write(b), self.stream.seek(ptr))
			self.newlines += b.count(b'\n') + (not b)
		self.newlines -= 1
		return self.stream.readline()

class FastO(IOBase):

	def __init__(self):
		stream = StringIO()
		self.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
		self.write = stream.write if sys.version_info[0] < 3 else lambda b: stream.write(b.encode())

class ostream:

	def __lshift__(self, a):
		if a == endl:
			sys.stdout.write('\n')
			sys.stdout.flush()
		else:
			sys.stdout.write(str(a))
		return self
(sys.stdin, sys.stdout) = (FastI(), FastO())
(flush, write) = (sys.stdout.flush, sys.stdout.write)
(cout, endl) = (ostream(), object())

def main():
	n = int(input())
	s = sorted((int(si) for si in input().split()))
	diffs = [0] * (n - 1)
	for i in range(n - 1):
		diffs[i] = s[i + 1] - s[i]
	diffs.sort()
	cumsum = [0] * n
	for i in range(n - 1):
		cumsum[i + 1] = cumsum[i] + diffs[i]
	q = int(input())
	for _ in range(q):
		(l, r) = map(int, input().split())
		res = (r - l + 1) * n
		ind = bisect_left(diffs, r - l + 1)
		res -= ind * (r - l + 1) - cumsum[ind]
		cout << res << ' '
main()


import sys
input = sys.stdin.readline
from bisect import bisect_left
n = int(input())
s = list(map(int, input().split()))
s.sort()
d = [s[i + 1] - s[i] for i in range(n - 1)]
d.sort()
pre = [0]
for x in d:
	pre.append(x + pre[-1])
q = int(input())
ans = []
for _ in range(q):
	(l, r) = map(int, input().split())
	w = r - l + 1
	x = bisect_left(d, w)
	ans.append(w * (n - x) + pre[x])
print(*ans)


import bisect
n = int(input())
ns = [int(x) for x in input().split()]
ns.sort()
diff = [ns[i] - ns[i - 1] for i in range(1, len(ns))]
diff.sort()
diffsm = [k[0] for k in [[0]] for i in diff if k.append(k.pop() + i) or True]
q = int(input())
for i in range(q):
	(l, r) = [int(x) for x in input().split()]
	l = r - l + 1
	nums = bisect.bisect(diff, l)
	if nums == 0:
		print((n - nums) * l)
		continue
	print(diffsm[nums - 1] + (n - nums) * l)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
n = int(input())
l = list(map(int, input().split()))
l.sort()
dif = []
for i in range(1, n):
	dif.append(l[i] - l[i - 1])
dif.sort()
s = SegmentTree(dif)
for i in range(int(int(input()))):
	(l, r) = map(int, input().split())
	t = len(dif) - countGreater(dif, len(dif), r - l + 2)
	ans = s.query(0, t - 1) + (len(dif) - t) * (r - l + 1)
	print(ans + r - l + 1, end=' ')


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_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=' ')


n = int(input())
S = list(set(list(map(int, input().split()))))
S.sort()
Q = int(input())
gaps = []
for i in range(1, len(S)):
	gaps.append(S[i] - S[i - 1])
gaps.sort()
total = []
for g in gaps:
	if total == []:
		total += [g]
	else:
		total += [total[-1] + g]
from bisect import *
for q in range(Q):
	(l, r) = map(int, input().split())
	lenth = r - l + 1
	ind = bisect_right(gaps, lenth)
	totalP = lenth * len(S)
	if ind == 0:
		print(totalP, end=' ')
	else:
		totalP -= lenth * ind - total[ind - 1]
		print(totalP, end=' ')


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()


from sys import stdin, stdout
n = int(stdin.readline())
l = list(map(int, stdin.readline().split()))
l.sort()
a = [0]
for i in range(1, n):
	a.append(l[i] - l[i - 1])
a.sort()
pre = [0] * (n + 1)
for i in range(n):
	pre[i + 1] = pre[i] + a[i]
q = int(stdin.readline())
for i in range(q):
	(l, r) = map(int, stdin.readline().split())
	length = r - l + 1
	(lo, hi) = (0, len(a) - 1)
	mid = -1
	while lo <= hi:
		mid = (lo + hi) // 2
		if mid == lo:
			if a[hi] < length:
				mid = hi
			break
		if length == a[mid]:
			break
		elif length < a[mid]:
			hi = mid - 1
		else:
			lo = mid
	ans = pre[mid + 1] + length + (n - mid - 1) * length
	stdout.write(str(ans) + ' ')


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)


import sys

class Q:

	def __init__(self, ll, i):
		self.ll = ll
		self.i = i

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def next(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = sys.stdin.readline().split()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_int(self):
		return int(self.next())

	def solve(self):
		n = self.next_int()
		x = sorted([self.next_int() for _ in range(0, n)])
		df = sorted([x[i] - x[i - 1] for i in range(1, n)])
		qq = []
		q = self.next_int()
		for _ in range(0, q):
			l = self.next_int()
			r = self.next_int()
			qq.append(Q(r - l, _))
		qq = sorted(qq, key=lambda x: x.ll)
		ad = 0
		i = 0
		for qt in qq:
			while i < len(df) and df[i] <= qt.ll:
				ad += df[i]
				i += 1
			qt.ans = ad + (qt.ll + 1) * (n - i)
		print(' '.join(map(lambda x: str(x.ans), sorted(qq, key=lambda x: x.i))))
Main().solve()


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_left as bl
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) = 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
	while start <= end:
		mid = (start + end) // 2
		if diffs[mid] > gap:
			start = mid + 1
		else:
			end = mid - 1
	if end == -1:
		pass
	else:
		maxrange += gap * (end + 1) - runninggaps[end]
	answers.append(maxrange)
print(*answers)


from bisect import *
n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n - 1):
	a[i] = a[i + 1] - a[i]
x = a.pop()
a.sort()
a.append(x)
for i in range(n - 1, 0, -1):
	a[i] = a[i - 1]
a[0] = 0
t = [0] * (n + 1)
for i in range(1, n):
	t[i] = t[i - 1] + (a[i] - a[i - 1]) * (n - i + 1)
m = int(input())
for i in range(m):
	(x, y) = map(int, input().split())
	x = y - x + 1
	pos = bisect_left(a, x) - 1
	print(t[pos] + (x - a[pos]) * (n - pos), end=' ')
print()


from __future__ import division, print_function
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) = map(int, input().split())
		ind = bisect_left(ediff, r - l + 1)
		print((r - l + 1) * (n - ind) + cumsum[ind], end=' ')
main()


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)


from bisect import *
n = int(input())
s = list(map(int, input().split()))
s.sort()
d = [s[i + 1] - s[i] for i in range(n - 1)]
d.sort()
pre = [0]
for x in d:
	pre.append(x + pre[len(pre) - 1])
q = int(input())
ans = []
for k in range(q):
	(l, r) = map(int, input().split())
	i = r - l + 1
	x = bisect_left(d, i)
	ans.append(i * (n - x) + pre[x])
print(*iter(ans))


import os
import sys
from io import BytesIO, IOBase
from bisect import *

def main():
	n = int(input())
	a = sorted(set(map(int, input().split())))
	n = len(a)
	b = []
	for i in range(n - 1):
		b.append(a[i + 1] - a[i])
	b.sort()
	dp = [0]
	for i in b:
		dp.append(i + dp[-1])
	for i in range(int(input())):
		(l, r) = map(int, input().split())
		z = bisect_left(b, r - l + 1)
		print(dp[z] + (n - z) * (r - l + 1), end=' ')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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())