Recently, Petya learned about a new game "Slay the Dragon". As the name suggests, the player will have to fight with dragons. To defeat a dragon, you have to kill it and defend your castle. To do this, the player has a squad of $n$ heroes, the strength of the $i$-th hero is equal to $a_i$.

According to the rules of the game, exactly one hero should go kill the dragon, all the others will defend the castle. If the dragon's defense is equal to $x$, then you have to send a hero with a strength of at least $x$ to kill it. If the dragon's attack power is $y$, then the total strength of the heroes defending the castle should be at least $y$.

The player can increase the strength of any hero by $1$ for one gold coin. This operation can be done any number of times.

There are $m$ dragons in the game, the $i$-th of them has defense equal to $x_i$ and attack power equal to $y_i$. Petya was wondering what is the minimum number of coins he needs to spend to defeat the $i$-th dragon.

Note that the task is solved independently for each dragon (improvements are not saved).


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — number of heroes.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$), where $a_i$ is the strength of the $i$-th hero.

The third line contains a single integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of dragons.

The next $m$ lines contain two integers each, $x_i$ and $y_i$ ($1 \le x_i \le 10^{12}; 1 \le y_i \le 10^{18}$) — defense and attack power of the $i$-th dragon.


-----Output-----

Print $m$ lines, $i$-th of which contains a single integer — the minimum number of coins that should be spent to defeat the $i$-th dragon.


-----Examples-----

Input
4
3 6 2 3
5
3 12
7 9
4 14
1 10
8 7
Output
1
2
4
0
2


-----Note-----

To defeat the first dragon, you can increase the strength of the third hero by $1$, then the strength of the heroes will be equal to $[3, 6, 3, 3]$. To kill the dragon, you can choose the first hero.

To defeat the second dragon, you can increase the forces of the second and third heroes by $1$, then the strength of the heroes will be equal to $[3, 7, 3, 3]$. To kill the dragon, you can choose a second hero.

To defeat the third dragon, you can increase the strength of all the heroes by $1$, then the strength of the heroes will be equal to $[4, 7, 3, 4]$. To kill the dragon, you can choose a fourth hero.

To defeat the fourth dragon, you don't need to improve the heroes and choose a third hero to kill the dragon.

To defeat the fifth dragon, you can increase the strength of the second hero by $2$, then the strength of the heroes will be equal to $[3, 8, 2, 3]$. To kill the dragon, you can choose a second hero.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Greedy algorithms


Solutions:
from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt, gcd
import bisect
import copy
from itertools import combinations
import sys

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
n = int(input())
a = get_array()
tot = sum(a)
x = set(a)
li = []
for ele in x:
	li.append(ele)
li.sort()
m = int(input())
n = len(li)
for i in range(m):
	(x, y) = get_ints()
	index1 = bisect.bisect_left(li, x + 1) - 1
	index2 = bisect.bisect_right(li, x)
	mini = inf
	if index1 < n and index1 >= 0:
		tot1 = tot - li[index1]
		req1 = max(0, x - li[index1])
		req2 = max(0, y - tot1)
		mini = min(mini, req1 + req2)
	if index2 < n:
		tot1 = tot - li[index2]
		req = max(0, y - tot1)
		mini = min(mini, req)
	print(mini)


import bisect
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
l = list(map(int, input().decode().split()))
l.sort()
t = 0
for i in l:
	t += i
for i in range(int(input())):
	(a, b) = input().decode().split()
	a = int(a)
	b = int(b)
	x = bisect.bisect_left(l, a)
	if x < n and l[x] == a:
		if t - l[x] >= b:
			print(0)
		else:
			print(b - (t - l[x]))
	elif x == n:
		ans = abs(l[x - 1] - a)
		if t - (a - ans) >= b:
			print(ans)
		else:
			print(b - (t - a))
	elif x == 0:
		if t - l[x] >= b:
			print(0)
		else:
			print(b - (t - l[x]))
	else:
		ans = 0
		ans1 = 0
		if t - l[x] >= b:
			ans = 0
		else:
			ans = b - (t - l[x])
		ans1 = abs(l[x - 1] - a)
		if t - (a - ans1) >= b:
			pass
		else:
			ans1 = b - (t - a)
		print(min(ans, ans1))


import bisect
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()

def li():
	return [int(i) for i in input().split()]

def lli(rows):
	return [li() for _ in range(rows)]

def si():
	return input()

def ii():
	return int(input())

def ins():
	return input().split()

def solve():
	n = II()
	a = LI()
	m = II()
	sa = sum(a)
	a.sort()
	for _ in range(m):
		(x, y) = LI()
		pos = bisect.bisect_left(a, x)
		if pos == 0:
			print(max(0, y - sa + a[0]))
		elif pos == n:
			print(x - a[-1] + max(0, y - sa + a[-1]))
		else:
			print(min(x - a[pos - 1] + max(0, y - sa + a[pos - 1]), max(0, y - sa + a[pos])))

def main():
	solve()
main()


import sys
from bisect import bisect_left
input = sys.stdin.readline
n = int(input())
li = list(map(int, input().split()))
li.sort()
strong = sum(li)
m = int(input())
for i in range(m):
	(a, b) = map(int, input().split())
	k = bisect_left(li, a)
	k = min(n - 1, k)
	k = max(0, k)
	ans = 0
	ans1 = max(0, a - li[k - 1]) + max(0, b - (strong - li[k - 1]))
	ans2 = max(0, a - li[k]) + max(0, b - (strong - li[k]))
	ans = min(ans1, ans2)
	print(ans)


from bisect import bisect_left as bl
import sys
input = sys.stdin.readline
w = int(input())
a = sorted(map(int, input().split()))
b = sum(a)
for i in range(int(input())):
	(x, y) = map(int, input().split())
	g = []
	c = bl(a, x)
	(d, e) = (0, 0)
	if c > len(a) - 1:
		c -= 1
	d = max(0, x - a[c]) + max(0, y - b + a[c])
	e = max(0, x - a[c - 1]) + max(0, y - b + a[c - 1])
	f = min(d, e)
	g.append(f)
	print(min(g))


import decimal
import math
import os
import sys
from collections import Counter
from io import BytesIO, IOBase
import bisect
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')

def ints_get():
	return map(int, input().strip().split())

def list_get():
	return list(map(int, sys.stdin.readline().strip().split()))

def chars_get():
	return list(map(str, sys.stdin.readline().strip().split()))

def output(to_be_printed, end='\n'):
	sys.stdout.write(str(to_be_printed) + end)

def main():
	n = int(input())
	a = list_get()
	a.sort()
	m = int(input())
	s = sum(a)
	v = []
	for _ in range(m):
		(x, y) = ints_get()
		val = bisect.bisect(a, x)
		ans = 10 ** 19
		if val == 0:
			p = s - a[0]
			ans = min(ans, max(0, y - p))
		elif val == n:
			p = s - a[n - 1]
			ans = min(ans, max(0, y - p) + max(0, x - a[n - 1]))
		else:
			p = s - a[val]
			ans = min(ans, max(0, y - p))
			p = s - a[val - 1]
			ans = min(ans, max(0, y - p) + max(0, x - a[val - 1]))
		print(ans)
	return
main()


import sys
import bisect
import collections
import copy
import itertools
import math
import functools
import operator
from heapq import heappop, heappush
input = sys.stdin.readline

def I():
	return input().rstrip()

def IS():
	return input().split()

def II():
	return int(input())

def IIS():
	return map(int, input().split())

def LIIS():
	return list(map(int, input().split()))
sys.setrecursionlimit(100000)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
	N = II()
	A = LIIS()
	A.sort()
	S = sum(A)
	M = II()
	for _ in range(M):
		(defense, attack) = IIS()
		res = INF
		pos = bisect.bisect_left(A, defense)
		if pos < N:
			res = min(res, max(0, defense - A[pos]) + max(0, attack - (S - A[pos])))
		if pos:
			res = min(res, max(0, defense - A[pos - 1]) + max(0, attack - (S - A[pos - 1])))
		print(res)
main()


from bisect import bisect_left as bl
import sys
input = sys.stdin.readline
n = int(input())
a = sorted(map(int, input().split()))
d = sum(a)
m = int(input())
c = []
for (x, y) in [list(map(int, input().split())) for _ in range(m)]:
	i = bl(a, x)
	j = bl(a, d - y)
	c.append(min((max(0, y - d + a[k]) + max(0, x - a[k]) for k in (i, j) * (max(i, j) < n) + (i - 1, j - 1))))
print(*c, sep='\n')


from bisect import bisect_left
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
t = sum(arr)
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	idx = bisect_left(arr, x)
	if idx == n:
		ans = abs(x - arr[-1]) + max(0, y - (t - arr[-1]))
	elif idx == 0 or arr[idx] == x:
		ans = max(0, y - (t - arr[idx]))
	else:
		(val1, val2) = (arr[idx - 1], arr[idx])
		ans1 = max(x - val1, 0) + max(0, y - (t - val1))
		ans2 = max(x - val2, 0) + max(0, y - (t - val2))
		ans = min(ans1, ans2)
	print(ans)


import sys
input = sys.stdin.buffer.readline

def find(A, x):
	n = len(A)
	if x < A[0]:
		return [-1, 0]
	elif x == A[0]:
		return [0, 0]
	elif x > A[-1]:
		return [n - 1, n]
	elif x == A[-1]:
		return [n - 1, n - 1]
	s = 0
	e = n - 1
	while s + 1 < e:
		m = (s + e) // 2
		if A[m] == x:
			return [m, m]
		elif A[m] > x:
			(s, e) = (s, m)
		else:
			(s, e) = (m, e)
	return [s, e]

def process(A, Q):
	S = sum(A)
	A = sorted(A)
	n = len(A)
	answer = []
	for (x, y) in Q:
		entry = float('inf')
		(x1, y1) = find(A, x)
		(x2, y2) = find(A, S - y)
		if x >= S - y:
			if x1 >= y2:
				entry = min(entry, x + y - S)
		if S - y >= x:
			if y1 >= 0 and x2 <= n - 1 and (x2 >= y1):
				entry = min(entry, 0)
		if max(y1, y2) <= n - 1:
			entry = min(entry, y + A[max(y1, y2)] - S)
		if min(x1, x2) >= 0:
			entry = min(entry, x - A[min(x1, x2)])
		answer.append(entry)
	return answer
t = int(input())
A = [int(x) for x in input().split()]
m = int(input())
Q = []
for i in range(m):
	(x, y) = [int(x) for x in input().split()]
	Q.append([x, y])
for x in process(A, Q):
	print(x)


from sys import stdin
from bisect import bisect
n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
arr.sort()
s = sum(arr)
for _ in range(int(stdin.readline())):
	(x, y) = map(int, stdin.readline().split())
	a = bisect(arr, x)
	X = arr[a - 1]
	if a - 1 <= 0:
		X = arr[a - 1]
	Y = s - X
	v = 0
	if X < x:
		v += x - X
	if Y < y:
		v += y - Y
	if a < n:
		if s - arr[a] < y:
			v = min(v, y - (s - arr[a]))
		else:
			v = 0
	print(v)


import math
import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType
from collections import defaultdict
BUFSIZE = 8192
from bisect import bisect_left
from bisect import bisect_right

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')
for i in range(1):
	n = int(input())
	b = list(map(int, input().split()))
	b.sort()
	s = sum(b)
	m = int(input())
	for i in range(m):
		(l, r) = map(int, input().split())
		ans = float('inf')
		if s - r <= l:
			ind = bisect_left(b, s - r)
			if ind != 0:
				ans = min(ans, l - b[ind - 1])
			ind1 = bisect_left(b, l)
			if ind1 != 0:
				if b[ind1 - 1] >= s - r:
					ans = min(ans, l + r - s)
			ind2 = bisect_right(b, l - 1)
			if ind2 != n:
				ans = min(ans, r - s + b[ind2])
		else:
			ind = bisect_left(b, l)
			if ind != 0:
				ans = min(ans, l - b[ind - 1])
			ind2 = ind = bisect_left(b, s - r)
			if ind2 != 0:
				if b[ind2 - 1] >= l:
					ans = 0
			try:
				ans = min(ans, r - s + b[bisect_right(b, s - r - 1)])
			except:
				pass
		print(ans)


import os
import sys
from io import BytesIO, IOBase
import math as mt
import itertools as it
import operator as op
import bisect as bs
import heapq as hp
from functools import reduce
from io import BytesIO, IOBase
from collections import deque, defaultdict, OrderedDict, Counter, ChainMap, _chain
(maxx, localsys, mod) = (1 << 60, 0, int(1000000000.0 + 7))

def nCr(n, r):
	return reduce(op.mul, range(n - r + 1, n + 1), 1) // mt.factorial(r)

def ceil(a, b):
	return (a + b - 1) // b

def lcm(a, b):
	return a * b // mt.gcd(a, b)
gcdm = lambda *args: reduce(mt.gcd, args, 0)

def lcm(a, b):
	return a * b // mt.gcd(a, b)
lcmm = lambda *args: reduce(lcm, args, 1)
_str = str
str = lambda x=b'': x if type(x) is bytes else _str(x).encode()
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))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return map(int, input().split())
from bisect import bisect_left

def search(A, key):
	return bisect_left(A, key)

def solve(defense, attack):
	idx = bisect_left(A, defense)
	mx = defense + attack
	for j in range(idx - 1, idx + 2):
		if 0 <= j < len(A):
			mx = min(mx, max(0, defense - A[j]) + max(0, attack - (tot - A[j])))
	return mx
(n,) = maps()
A = [*maps()]
(m,) = maps()
tot = sum(A)
A.sort()
for i in range(m):
	(defense, attack) = maps()
	print(solve(defense, attack))


def bin_search(lst, n):
	lo = 0
	hi = len(lst) - 1
	while lo < hi:
		mid = (lo + hi) // 2
		if lst[mid] >= n:
			hi = mid
		else:
			lo = mid + 1
	if lst[lo] >= n:
		return lo
	else:
		return -1
from bisect import bisect_left
import sys
input = sys.stdin.readline
n = int(input())
a = [*map(int, input().split())]
a.sort()
sz = len(a)
sm = sum(a)
m = int(input())
dragon = []
ans = [None for _ in range(m)]
for i in range(m):
	(x, y) = map(int, input().split())
	bs = bisect_left(a, x)
	if bs != sz:
		coins = 0
		b1 = bs
		b2 = bs - 1
		rem = sm - a[b1]
		coins += max(y - rem, 0)
		coin = 1 << 60
		if b2 >= 0:
			coin = x - a[b2]
			rem = sm - a[b2]
			coin += max(y - rem, 0)
		ans[i] = min(coin, coins)
	else:
		total_req = x - a[sz - 1]
		total_req += max(0, y - (sm - a[sz - 1]))
		ans[i] = total_req
sys.stdout.write('\n'.join(map(str, ans)) + '\n')


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')
from bisect import bisect_right, bisect_left
(n, a, m) = (int(input()), sorted([*map(int, input().split())]), int(input()))
total_strength = sum(a)
dragon_stats = [[int(i) for i in input().split()] for j in range(m)]
for (defense, attack) in dragon_stats:
	hero_index = bisect_left(a, defense)
	if hero_index == n:
		hero_strength = a[-1]
		remaining_strength = total_strength - hero_strength
		print(defense - hero_strength + max(0, attack - remaining_strength))
	elif hero_index == 0:
		hero_strength = a[0]
		remaining_strength = total_strength - hero_strength
		print(max(0, defense - hero_strength) + max(0, attack - remaining_strength))
	else:
		hero_strength = a[hero_index]
		remaining_strength = total_strength - hero_strength
		ans = max(0, defense - hero_strength) + max(0, attack - remaining_strength)
		hero_strength = a[hero_index - 1]
		remaining_strength = total_strength - hero_strength
		ans1 = max(0, defense - hero_strength) + max(0, attack - remaining_strength)
		print(min(ans, ans1))


import sys
input = sys.stdin.readline
from bisect import bisect
n = int(input())
a = sorted([*map(int, input().split())])
ss = sum(a)
for i in range(int(input())):
	(x, y) = map(int, input().split())
	b = bisect(a, x) - 1
	ff = a[b]
	if b == -1:
		print(max(y - (ss - a[0]), 0))
	elif ff == x:
		print(max(y - (ss - x), 0))
	elif b + 1 < n:
		fff = a[b + 1]
		if y - (ss - fff) <= 0:
			print(0)
		else:
			print(min(y - (ss - fff), max(y - (ss - ff), 0) + (x - ff)))
	else:
		print(max(y - (ss - ff), 0) + (x - ff))


import sys
import bisect
import math
input = sys.stdin.readline
n = int(input())
a = [*map(int, input().split())]
a.sort()
m = int(input())
s = sum(a)
for _ in range(m):
	(x, y) = map(int, input().split())
	ans = 0
	ind = bisect.bisect_left(a, x)
	ans += max(0, x - a[ind - 1])
	ans += max(0, y - (s - a[ind - 1]))
	ans1 = math.inf
	if ind != len(a):
		ans1 = max(0, x - a[ind])
		ans1 += max(0, y - (s - a[ind]))
	print(min(ans, ans1))


import sys
from bisect import bisect_left
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
dragon = []
for i in range(m):
	(defense, attack) = map(int, sys.stdin.readline().split())
	dragon.append((defense, attack))
a.sort()
total = sum(a)
for enemy in dragon:
	defense = enemy[0]
	attack = enemy[1]
	loc = bisect_left(a, defense)
	ans = 0
	if loc == 0:
		key = a[0]
		if total - key < attack:
			ans += attack - (total - key)
	elif loc == n:
		key = a[-1]
		ans += defense - key
		if total - key < attack:
			ans += attack - (total - key)
	else:
		case1 = 0
		key = a[loc]
		if total - key < attack:
			case1 += attack - (total - key)
		case2 = 0
		key2 = a[loc - 1]
		case2 += defense - key2
		if total - key2 < attack:
			case2 += attack - (total - key2)
		ans = min(case1, case2)
	print(ans)


from sys import stdin, stdout
from bisect import bisect_left as bl
n = int(input())
a = []
ss = 0
for ele in map(int, input().split()):
	a.append(ele)
	ss += ele
a.sort()
m = int(input())
anss = []
while m:
	m -= 1
	(x, y) = map(int, input().split())
	ind = bl(a, x)
	if ind > 0 and ind < n:
		ans1 = x - a[ind - 1]
		if ss - a[ind - 1] < y:
			ans1 += y - (ss - a[ind - 1])
		ans2 = 0
		if ss - a[ind] < y:
			ans2 += y - (ss - a[ind])
		anss.append(min(ans1, ans2))
	elif ind == 0:
		ans = 0
		if ss - a[ind] < y:
			ans += y - (ss - a[ind])
		anss.append(ans)
	else:
		ans1 = x - a[ind - 1]
		if ss - a[ind - 1] < y:
			ans1 += y - (ss - a[ind - 1])
		anss.append(ans1)
print(*anss, sep='\n')


import sys
input = sys.stdin.readline
import bisect
t = 1
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	a.sort()
	m = int(input())
	for i in range(m):
		(x, y) = map(int, input().split())
		j = bisect.bisect_right(a, x)
		if j == n:
			ans = x - a[-1] + max(0, y + a[-1] - s)
		elif j == 0:
			ans = max(0, y + a[0] - s)
		else:
			ans = min(max(0, y + a[j] - s), x - a[j - 1] + max(0, y + a[j - 1] - s))
		sys.stdout.write(str(ans) + '\n')


from bisect import bisect
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
(suma, costs) = (sum(a), [])
a_set = set(a)
a = sorted(a_set)
n = len(a)
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x in a_set:
		cost = max(0, y - (suma - x))
	else:
		if x > a[-1]:
			pos = n
		else:
			pos = bisect(a, x)
		cost = float('inf')
		if pos > 0:
			nou_cost = x - a[pos - 1] + max(0, y - (suma - a[pos - 1]))
			cost = min(cost, nou_cost)
		if pos < n:
			nou_cost = max(0, y - (suma - a[pos]))
			cost = min(cost, nou_cost)
	costs.append(str(cost))
sys.stdout.write('\n'.join(costs) + '\n')


from bisect import bisect_right, bisect
n = int(input())
a = list(map(int, input().split()))
a.sort()
su = sum(a)
a.append(10 ** 13)
li = []
m = int(input())
for i in range(m):
	(x, y) = map(int, input().split())
	li.append([x, y])
for i in range(m):
	x = li[i][0]
	y = li[i][1]
	ind = 0
	z = 0
	ind = bisect(a, x)
	if ind != 0:
		if a[ind - 1] == x:
			if su - x >= y:
				print(0)
			else:
				print(y - su + x)
		elif z == 0:
			ans1 = x - a[ind - 1]
			if su - a[ind - 1] >= y:
				pass
			else:
				ans1 += y - su + a[ind - 1]
			ans2 = 0
			if su - a[ind] >= y:
				pass
			else:
				ans2 += y - su + a[ind]
			print(min(ans1, ans2))
		else:
			ans1 = x - a[ind]
			if su - a[ind] >= y:
				pass
			else:
				ans1 += y - su + a[ind]
			print(ans1)
	else:
		ans1 = 0
		if su - a[ind] >= y:
			pass
		else:
			ans1 += y - su + a[ind]
		print(ans1)


import sys
import bisect
input = sys.stdin.readline
n = int(input())
a = sorted(list(map(int, input().split())))
m = int(input())
total = sum(a)
for _ in range(m):
	(x, y) = map(int, input().split())
	var = bisect.bisect_right(a, x)
	if var == n:
		sys.stdout.write(str(x - a[-1] + max(0, y - total + a[-1])) + '\n')
	elif var == 0:
		sys.stdout.write(str(max(0, y - total + a[0])) + '\n')
	else:
		sys.stdout.write(str(min(x - a[var - 1] + max(0, y - total + a[var - 1]), max(0, y - total + a[var]))) + '\n')


import sys
import bisect
input = sys.stdin.readline
n = int(input())
a = sorted(map(int, input().split()))
s = sum(a)
for i in range(int(input())):
	(x, y) = map(int, input().split())
	p = bisect.bisect_left(a, x) - 1
	ans1 = 2 * 10 ** 18
	if p != -1:
		ans1 = x - a[p] + max(y - s + a[p], 0)
	ans2 = 2 * 10 ** 18
	if p != n - 1:
		ans2 = max(y - s + a[p + 1], 0)
	print(min(ans1, ans2))


from sys import stdin
from bisect import bisect_left
input = stdin.readline
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
m = int(input())
s = sum(arr)
for i in range(m):
	(x, y) = map(int, input().split())
	if s <= y or s > y:
		ans = float('inf')
		pos = bisect_left(arr, x)
		if pos < n:
			g = max(0, y - (s - arr[pos])) + max(0, x - arr[pos])
			ans = min(ans, g)
		pos = pos - 1
		if pos >= 0:
			g = max(0, x - arr[pos]) + max(0, y - (s - arr[pos]))
			ans = min(ans, g)
		print(ans)


from collections import Counter, defaultdict
from sys import stdin, stdout
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import OrderedDict
from bisect import bisect_left, bisect_right
mod = 998244353

def mapinput():
	return map(int, input().split())

def listinput():
	return [int(i) for i in input().split()]

def intinput():
	return int(input())

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

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	ans = []
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans

def writ(ss):
	stdout.write(str(ss) + '\n')

def mult(a, b, mod):
	return a % mod * (b % mod) % mod
try:
	n = intinput()
	arr = listinput()
	su = sum(arr)
	arr.sort()
except:
	print('HAHAHA1')
for test in range(intinput()):
	(x, y) = mapinput()

	def solve(arr, x, y):
		lowerbound = bisect_left(arr, x)
		aaa = [lowerbound, lowerbound - 1]
		answers = 9999999999999999999999999999999999
		for aa in aaa:
			if 0 <= aa < n:
				if arr[aa] >= x:
					m2 = max(0, y - (su - arr[aa]))
				else:
					m2 = max(0, max(0, x - arr[aa]) + max(0, y - (su - arr[aa])))
				answers = min(answers, m2)
		return answers
	writ(solve(arr, x, y))


from sys import stdin, stdout
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from bisect import bisect_left, bisect_right
mod = 998244353

def mapinput():
	return map(int, input().split())

def listinput():
	return [int(i) for i in input().split()]

def intinput():
	return int(input())

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

def writ(ss):
	stdout.write(str(ss) + '\n')
n = intinput()
arr = listinput()
su = sum(arr)
arr.sort()
for test in range(intinput()):

	def solve():
		(x, y) = mapinput()
		lowerbound = bisect_left(arr, x)
		aaa = [lowerbound, lowerbound - 1]
		answers = 9999999999999999999999999999999999
		for aa in aaa:
			if 0 <= aa < n:
				m2 = max(0, max(0, x - arr[aa]) + max(0, y - (su - arr[aa])))
				answers = min(answers, m2)
		return answers
	writ(solve())


import sys
import bisect
t_str = sys.stdin.readline().rstrip()
if t_str != '':
	n = int(t_str)
	h = [int(a) for a in sys.stdin.readline().rstrip().split(' ')]
	h = sorted(h)
	d = int(sys.stdin.readline().rstrip())
	total = sum(h)
	while d > 0:
		left = None
		right = None
		(x, y) = [int(a) for a in sys.stdin.readline().rstrip().split(' ')]
		ind = bisect.bisect_left(h, x)
		if ind != 0:
			left = h[ind - 1]
		if ind != n:
			right = h[ind]
		result = None
		if left is not None:
			result = x - left
			if total - left < y:
				result += y - total + left
		if right is not None:
			if result is not None:
				diff = 0
				if total - right < y:
					diff = y - total + right
				result = min(result, diff)
			elif total - right < y:
				result = y - total + right
			else:
				result = 0
		print(result)
		d -= 1


from sys import stdin
from bisect import bisect_left
count_h = stdin.readline()
heroes = list(map(int, stdin.readline().split(' '))) + [1000000000001]
heroes.sort()
heroes_sum = sum(heroes[:-1])
for i in range(int(stdin.readline())):
	(p, a) = map(int, stdin.readline().split(' '))
	bis = bisect_left(heroes, p)
	(hero_under, hero_above) = (heroes[bis], heroes[bis - 1 * (bis != 0)])
	(protect_1, attack_1) = (p - hero_under, a - (heroes_sum - hero_under))
	(protect_2, attack_2) = (p - hero_above, a - (heroes_sum - hero_above))
	print(min(protect_1 * (protect_1 > 0) + attack_1 * (attack_1 > 0), protect_2 * (protect_2 > 0) + attack_2 * (attack_2 > 0)))


from bisect import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

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

def ma():
	return map(int, input().split())
t = 1
while t:
	t -= 1
	n = inp()
	a = lis()
	a.sort()
	m = inp()
	su = sum(a)
	for i in range(m):
		(x, y) = ma()
		rr = 0
		z = bisect_left(a, x)
		if z >= n:
			z = n - 1
		if a[z] < x:
			rr += x - a[z]
		su1 = su - a[z]
		if su1 < y:
			rr += y - su1
		if z != 0:
			rr1 = 0
			if a[z - 1] < x:
				rr1 += x - a[z - 1]
			su1 = su - a[z - 1]
			if su1 < y:
				rr1 += y - su1
			rr = min(rr, rr1)
		print(rr)


def var():
	return map(int, input().split())

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

def inp():
	return int(input())
import math
import copy
from collections import defaultdict, deque
import heapq
import sys
sys.setrecursionlimit(10 ** 5)
mod = 10 ** 9 + 7
input = sys.stdin.buffer.readline
h = inp()
heroP = a()
heroP.sort()
preS = [0]
for power in heroP:
	preS.append(preS[-1] + power)
d = inp()
for i in range(d):
	(defense, att) = var()
	if defense > heroP[-1]:
		print(defense - heroP[-1] + max(0, att - preS[h - 1]))
		continue
	l = 0
	r = h - 1
	while l <= r:
		m = l + (r - l) // 2
		if heroP[m] >= defense:
			index = m
			r = m - 1
		else:
			l = m + 1
	if heroP[index] == defense:
		print(max(0, att - preS[-1] + heroP[index]))
		continue
	if index > 0:
		coin = min(att - preS[-1] + heroP[index], defense - heroP[index - 1] + max(0, att - preS[-1] + heroP[index - 1]))
	else:
		coin = att - preS[-1] + heroP[index]
	print(max(0, coin))


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')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(a, b):
	return a * b // gcd(a, b)

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

class Result:

	def __init__(self, index, value):
		self.index = index
		self.value = value

class BinarySearch:

	def __init__(self):
		pass

	@staticmethod
	def greater_than(num: int, func, size: int=1):
		if isinstance(func, list):
			index = bisect_right(func, num)
			if index == len(func):
				return Result(None, None)
			else:
				return Result(index, func[index])
		else:
			(alpha, omega) = (0, size - 1)
			if func(omega) <= num:
				return Result(None, None)
			while alpha < omega:
				if func(alpha) > num:
					return Result(alpha, func(alpha))
				if omega == alpha + 1:
					return Result(omega, func(omega))
				mid = (alpha + omega) // 2
				if func(mid) > num:
					omega = mid
				else:
					alpha = mid

	@staticmethod
	def less_than(num: int, func, size: int=1):
		if isinstance(func, list):
			index = bisect_left(func, num) - 1
			if index == -1:
				return Result(None, None)
			else:
				return Result(index, func[index])
		else:
			(alpha, omega) = (0, size - 1)
			if func(alpha) >= num:
				return Result(None, None)
			while alpha < omega:
				if func(omega) < num:
					return Result(omega, func(omega))
				if omega == alpha + 1:
					return Result(alpha, func(alpha))
				mid = (alpha + omega) // 2
				if func(mid) < num:
					alpha = mid
				else:
					omega = mid
bs = BinarySearch()
for _ in range(int(input()) if not True else 1):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	total = sum(a)
	for i in range(int(input())):
		ans = float('inf')
		(df, at) = map(int, input().split())
		ind1 = bs.less_than(df + 1, a).value
		if ind1 is not None:
			tt = total - ind1
			extra = 0
			if tt < at:
				extra = at - tt
			ans = min(ans, abs(df - ind1) + extra)
		ind2 = bs.greater_than(df - 1, a).value
		if ind2 is not None:
			extra = 0
			tt = total - ind2
			if tt < at:
				extra = at - tt
			ans = min(ans, extra)
		print(ans)


from math import sqrt, gcd, ceil, floor, log, factorial
from itertools import permutations, combinations
from collections import Counter, defaultdict
import collections, sys, threading
import collections, sys, threading
from bisect import *
input = sys.stdin.readline

def ii():
	return int(input())

def si():
	return input()

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

def msi():
	return map(str, input().split())

def li():
	return list(mi())

def f(n, a, x, y, summ):
	ll = bisect_left(a, x, 0, n)
	if ll == n:
		req = x - a[ll - 1]
		power = max(y - summ + a[ll - 1], 0)
		return req + power
	elif ll > 0:
		req = min(max(0, x - a[ll]) + max(0, y - summ + a[ll]), max(0, x - a[ll - 1]) + max(0, y - summ + a[ll - 1]))
		return req
	else:
		power = max(y - sum(a) + a[ll], 0) + max(x - a[ll], 0)
		return power
n = ii()
a = li()
a.sort()
summ = sum(a)
m = ii()
for i in range(m):
	(x, y) = mi()
	print(f(n, a, x, y, summ))


import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
from math import cos, sin
from itertools import permutations
from operator import itemgetter
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')
n = int(input())
a = list(map(int, input().split()))
a.sort()
s = sum(a)
for _ in range(int(input())):
	(d, at) = map(int, input().split())
	x = bisect_left(a, d)
	x1 = x2 = x3 = a[0]
	if x != n:
		x2 = a[x]
	if x != 0:
		x1 = a[x - 1]
	if x < n - 1:
		x3 = a[x + 1]
	ans = float('inf')
	ans = min(ans, max(0, at - (s - x1)) + max(0, d - x1))
	ans = min(ans, max(0, at - (s - x2)) + max(0, d - x2))
	ans = min(ans, max(0, at - (s - x3)) + max(0, d - x3))
	print(ans)


import sys
input = sys.stdin.buffer.readline

def inp():
	return int(input())

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

def input_string():
	s = input()
	return list(s[:len(s) - 1])

def input_int_gen():
	return map(int, input().split())
from collections import defaultdict
from bisect import bisect_left
tests = 1
res = []
for _ in range(tests):
	n = inp()
	a = input_list()
	a.sort()
	sumi = sum(a)
	m = inp()
	for _ in range(m):
		(defense, attack) = input_int_gen()
		i = bisect_left(a, defense)
		inc_defense = sumi + defense + attack
		inc_attack = sumi + attack + defense
		if i < n:
			inc_defense = max(0, defense - a[i]) + max(attack - (sumi - a[i]), 0)
		i -= 1
		if i >= 0:
			inc_attack = max(0, defense - a[i]) + max(attack - (sumi - a[i]), 0)
		print(str(min(inc_defense, inc_attack)))


import bisect
from sys import stdin

def A():

	def g(l, r, t):
		global res, n
		if len(res) == n:
			return
		if l == r == 0:
			res.append(t)
			return
		if l > 0:
			g(l - 1, r, t + '(')
		if r > l:
			g(l, r - 1, t + ')')
	t = int(stdin.readline())
	while t:
		t -= 1
		global res, n
		n = int(input())
		res = []
		g(n, n, '')
		for i in range(0, n):
			print(res[i])

def B():
	t = int(stdin.readline())
	while t:
		t -= 1
		(a, b, c, m) = [int(x) for x in stdin.readline().split()]
		maxx = max(a, b, c)
		minn = min(a, b, c)
		med = a + b + c - maxx - minn
		if m > a + b + c - 3:
			print('NO')
		elif minn > m:
			maxx -= m + 1
			if maxx - (minn + med) > 2:
				print('NO')
			else:
				print('YES')
		elif med > m:
			maxx -= m + 1
			if maxx - (minn + med) > 2:
				print('NO')
			else:
				print('YES')
		else:
			print('YES')

def C():
	n = int(input())
	a = [int(x) for x in stdin.readline().split()]
	m = int(input())
	a.sort()
	total = sum(a)
	for i in range(m):
		(x, y) = [int(x) for x in stdin.readline().split()]
		k = bisect.bisect_left(a, x, 0, n)
		k = min(n - 1, k)
		if a[k] > x:
			k2 = abs(a[k - 1] - x)
			k3 = total - a[k]
			k4 = total - a[k - 1]
			k3 = y - k3
			k4 = y - k4
			res_1 = max(0, k3)
			res_2 = max(0, k4) + k2
			print(min(res_1, res_2))
		else:
			k2 = min(0, a[k] - x)
			k4 = total - a[k]
			k4 = y - k4
			res_2 = max(0, k4) - k2
			print(res_2)
C()


import sys
input = sys.stdin.readline
import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import bisect
inf = float('inf')
n = int(input())
A = list(map(int, input().split()))
A.sort()
total = sum(A)

def solve(defense, attack):
	ans = inf
	j = bisect.bisect_left(A, defense)
	for k in range(j - 1, j + 2):
		if 0 <= k < len(A):
			ans = min(ans, max(0, defense - A[k]) + max(0, attack - (total - A[k])))
	return ans
m = int(input())
for _ in range(m):
	(defense, attack) = map(int, input().split())
	print(solve(defense, attack))


from sys import *
from bisect import *
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
a.sort()
sm = sum(a)
tot = sm
for _ in range(int(stdin.readline())):
	sm = tot
	(defence, attack) = map(int, stdin.readline().split())
	right = bisect_right(a, defence)
	ans = 0
	if right == n:
		plus = defence - a[-1]
		ans += plus
		rem = sm - a[-1]
		if rem < attack:
			plus = attack - rem
			val = a[0]
			ans += plus
	elif right == 0:
		rem = sm - a[right]
		if rem < attack:
			plus = attack - rem
			val = a[0]
			ans += plus
	else:
		val = a[right - 1]
		plus = defence - val
		ans += plus
		sm += plus
		rem = sm - (val + plus)
		cnt = 1
		if rem < attack:
			plus = attack - rem
			val = a[0]
			ans += plus
			sm += plus
			cnt += 1
		curr = 0
		sm = tot
		rem = sm - a[right]
		if rem < attack:
			plus = attack - rem
			val = a[0]
			curr += plus
		ans = min(ans, curr)
	stdout.write(str(ans) + '\n')


from bisect import bisect_left
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()
s = sum(a)
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	b = bisect_left(a, x)
	if b == 0:
		c = max(y - (s - a[b]), 0)
	elif b == len(a):
		c = max(y - (s - a[b - 1]), 0) + max(x - a[b - 1], 0)
	else:
		c = min(max(y - (s - a[b - 1]), 0) + max(x - a[b - 1], 0), max(y - (s - a[b]), 0))
	sys.stdout.write(str(c) + '\n')


import sys
input = sys.stdin.readline
import bisect
n = int(input())
a = list(map(int, input().split()))
a.sort()
sm = sum(a)
m = int(input())
b = []
ans = [0] * m
for i in range(m):
	(x, y) = map(int, input().split())
	idx = bisect.bisect_left(a, x)
	if idx >= n:
		idx -= 1
	res = max(0, x - a[idx])
	rem = sm - a[idx]
	res += max(0, y - rem)
	if idx > 0:
		idx -= 1
		cur = max(0, x - a[idx])
		rem = sm - a[idx]
		cur += max(0, y - rem)
		res = min(res, cur)
	ans[i] = str(res)
print('\n'.join(ans))


import sys
input = sys.stdin.readline

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

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import copy, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, chain, combinations, groupby
from operator import itemgetter
from types import GeneratorType
from typing import Iterable, TypeVar, Union
for _ in range(1):
	n = II()
	a = LI()
	m = II()
	a.sort()
	s = sum(a)
	for q in range(m):
		(r, t) = LI()
		left = s
		if r > a[-1]:
			ans = r - a[-1]
			left -= a[-1]
			ans += max(t - left, 0)
			print(ans)
		else:
			ind = bisect_left(a, r)
			left -= a[ind]
			ans = max(t - left, 0)
			if ind > 0:
				temp = r - a[ind - 1]
				left = s - a[ind - 1]
				temp += max(t - left, 0)
				ans = min(ans, temp)
			print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from bisect import bisect_left as bl
n = int(input())
l = tuple(sorted(map(int, input().split())))
s = sum(l)
m = int(input())
ans = [0] * m
for _ in range(m):
	(x, y) = map(int, input().split())
	k = 0
	i = bl(l, x)
	if i == n:
		p = s - l[-1]
		k = x - l[-1]
		if p < y:
			k += y - p
	else:
		p = s - l[i]
		if p < y:
			k = y - p
		if i != 0:
			q = x - l[i - 1]
			p = s - l[i - 1]
			if p < y:
				q += y - p
			k = min(k, q)
	ans[_] = k
print(*ans, sep='\n')


from sys import stdin
from bisect import bisect_left
input = stdin.readline
count_h = int(input())
heroes = [int(x) for x in input().split()] + [1000000000001]
heroes.sort()
heroes_sum = sum(heroes[:-1])
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	l = bisect_left(heroes, x)
	print(min(max(0, x - heroes[l - 1]) + max(0, y - heroes_sum + heroes[l - 1]), max(0, x - heroes[l]) + max(0, y - heroes_sum + heroes[l])))


import sys
import getpass
import bisect
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')
M9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def minus_one(arr):
	return [x - 1 for x in arr]

def minus_one_matrix(mrr):
	return [[x - 1 for x in row] for row in mrr]

def solve_():
	arr = list(map(int, input().split()))
	arr.sort()
	sumarr = sum(arr)
	k = int(input())
	for _ in range(k):
		(required_attack, required_defence) = list(map(int, input().split()))
		minres = 10 ** 19
		idx = bisect.bisect_left(arr, required_attack)
		for addn in [0, -1]:
			idx += addn
			if idx < 0:
				idx += 1
			while idx >= len(arr):
				idx -= 1
			attack = arr[idx]
			defend = sumarr - attack
			r1 = max(0, required_attack - attack)
			r2 = max(0, required_defence - defend)
			res = r1 + r2
			minres = min(minres, res)
		print(minres)
for case_num in [0]:
	k = int(input())
	res = solve()


from bisect import bisect_left
import sys
input = sys.stdin.readline
n = int(input())
l = sorted(list(map(int, input().split())))
m = int(input())
tot = sum(l)
for _ in range(m):
	(x, y) = map(int, input().split())
	p = bisect_left(l, x) - 1
	if p == -1:
		p = 0
		print(max(0, y - tot + l[0]))
	elif p == n - 1:
		print(max(0, x - l[n - 1]) + max(0, y - tot + l[n - 1]))
	else:
		res1 = max(0, x - l[p])
		res1 += max(0, y - tot + l[p])
		res2 = max(0, x - l[p + 1])
		res2 += max(0, y - tot + l[p + 1])
		print(min(res1, res2))


import sys
input = sys.stdin.buffer.readline

def mayorigual(heroes, n):
	izq = 0
	der = len(heroes) - 1
	ans = -1
	while izq <= der:
		med = izq + (der - izq) // 2
		if heroes[med] >= n:
			ans = heroes[med]
			der = med - 1
		else:
			izq = med + 1
	return ans

def menorigual(heroes, n):
	izq = 0
	der = len(heroes) - 1
	ans = -1
	while izq <= der:
		med = izq + (der - izq) // 2
		if heroes[med] <= n:
			ans = heroes[med]
			izq = med + 1
		else:
			der = med - 1
	return ans

def solve(heroes, suma, x, y):
	a1 = mayorigual(heroes, x)
	a2 = menorigual(heroes, x)
	ans = 0
	if a1 == -1:
		ans += x - a2
		if suma - a2 < y:
			ans += y - (suma - a2)
	elif a2 == -1:
		if suma - a1 < y:
			ans += y - (suma - a1)
	else:
		sol1 = x - a2
		if suma - a2 < y:
			sol1 += y - (suma - a2)
		sol2 = 0
		if suma - a1 < y:
			sol2 += y - (suma - a1)
		ans = min(sol1, sol2)
	return ans
h = int(input())
heroes = list(map(int, input().split()))
heroes.sort()
suma = sum(heroes)
d = int(input())
for i in range(d):
	(x, y) = map(int, input().split())
	print(solve(heroes, suma, x, y))


import sys
import os
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')
n = int(input())
l = list(map(int, input().split()))
l.sort()
max_ele = l[-1]
min_ele = l[0]
total = sum(l)
m = int(input())
for p in range(m):
	gold = 0
	(x, y) = map(int, input().split())
	if max_ele <= x:
		gold += x - max_ele
		gold += max(0, y - (total - max_ele))
		print(gold)
	elif min_ele >= x:
		gold = max(0, y - (total - min_ele))
		print(gold)
	else:
		left = 0
		right = n - 1
		found = -1
		while left <= right:
			mid = left + (right - left) // 2
			if l[mid] >= x:
				found = mid
				right = mid - 1
			else:
				left = mid + 1
		one = l[found]
		two = l[found - 1]
		diff1 = max(0, y - (total - one))
		diff2 = abs(x - two)
		diff2 += max(0, y - (total - two))
		gold = min(diff1, diff2)
		print(gold)


import sys
from sys import stdin
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, namedtuple
from math import gcd, ceil, floor
from itertools import combinations, permutations
input = sys.stdin.buffer.readline

def work(a, n, tot, x, y):
	ans = 0
	if a[-1] < x:
		ans += x - a[-1]
		tot -= a[-1]
		ans += max(0, y - tot)
		print(ans)
		return
	if a[0] >= x:
		tot -= a[0]
		ans += max(0, y - tot)
		print(ans)
		return
	idx = bisect_left(a, x)
	t1 = 0
	tot1 = tot - a[idx]
	t1 += max(0, y - tot1)
	t2 = float('inf')
	if idx - 1 >= 0:
		t2 = 0
		idx2 = idx - 1
		t2 += x - a[idx2]
		tot2 = tot - a[idx2]
		t2 += max(0, y - tot2)
	ans = min(t1, t2)
	print(ans)
	return

def main():
	test = 1
	for idt in range(test):
		n = int(input())
		a = list(map(int, input().split()))
		a.sort()
		tot = sum(a)
		m = int(input())
		for i in range(m):
			(x, y) = map(int, input().split())
			work(a, n, tot, x, y)
	return
main()


from sys import stdin, stdout, setrecursionlimit
from io import BytesIO, IOBase
from bisect import bisect_left as bl, bisect_right as br, bisect as bis
setrecursionlimit(10000)

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
		self.BUFSIZE = 8192

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

	def readline(self):
		while self.newlines == 0:
			a = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = a.count(b'\n') + (not a)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(a), 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')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
input = lambda : stdin.readline().rstrip('\r\n')
inp = lambda : int(input())
st = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
int_arr = lambda : list(map(int, input().strip().split()))
str_arr = lambda : list(map(str, input().split()))
get_str = lambda : map(str, input().strip().split())
get_int = lambda : map(int, input().strip().split())
get_float = lambda : map(float, input().strip().split())
mod = 1000000007
n = inp()
arr = int_arr()
tot = sum(arr)
arr.sort()
for _ in range(inp()):
	(x, y) = get_int()
	rem = tot - y
	yes = False
	(ans, ans1) = (float('inf'), float('inf'))
	if rem <= 0:
		yes = True
	rem = abs(rem)
	ind = bl(arr, x)
	ind1 = ind
	if ind == n:
		ind -= 1
		ind1 -= 1
	elif ind == 0:
		pass
	else:
		prev = arr[ind]
		ind1 = ind
		while ind1 >= 0 and arr[ind1] == prev:
			ind1 -= 1
		if ind1 < 0:
			ind1 = 0
	if yes:
		ans = rem + arr[ind1]
		ans1 = rem + arr[ind]
	else:
		if arr[ind1] > rem:
			ans = arr[ind1] - rem
		if arr[ind] > rem:
			ans1 = arr[ind] - rem
	if x - arr[ind1] > 0:
		if ans != float('inf'):
			ans += x - arr[ind1]
		else:
			ans = x - arr[ind1]
	elif ans == float('inf'):
		ans = 0
	if ind != n:
		if x - arr[ind] > 0:
			if ans1 != float('inf'):
				ans1 += x - arr[ind]
			else:
				ans1 = x - arr[ind]
		elif ans1 == float('inf'):
			ans1 = 0
		ans = min(ans1, ans)
	print(ans)


import sys
from bisect import bisect_right as bis

def main():
	t = 1
	for _ in range(t):
		n = int(input())
		ar = sorted(list(map(int, input().split())))
		s = sum(ar)
		for _ in range(int(input())):
			(x, y) = map(int, input().split())
			k = bis(ar, x)
			sp = y - s
			if k == n:
				xij = x - ar[-1]
				yij = max(0, sp + ar[-1])
				print(xij + yij)
			elif k == 0:
				print(max(0, sp + ar[0]))
			else:
				xij = x - ar[k - 1]
				yij = max(0, sp + ar[k - 1])
				ans1 = xij + yij
				ans2 = max(0, sp + ar[k])
				print(min(ans1, ans2))
import os
import sys
from io import BytesIO, IOBase
_str = str
str = lambda x=b'': x if type(x) is bytes else _str(x).encode()
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 os, sys
from io import BytesIO, IOBase
BUFSIZE = 8164

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 = IOWrapper(sys.stdin)
input = lambda : sys.stdin.readline().rstrip('\r\n')
from bisect import bisect_left as b
n = int(input())
a = sorted([int(i) for i in input().split()])
sum_of_a = sum(a)
for i in range(int(input())):
	(x, y) = map(int, input().split())
	ind = b(a, x)
	if ind < n and a[ind] == x:
		print(max(0, y - sum_of_a + x))
	elif ind == 0:
		print(max(0, y - sum_of_a + a[0]))
	elif ind == n:
		print(max(0, y - sum_of_a + a[-1]) + x - a[-1])
	else:
		print(min(max(0, y - sum_of_a + a[ind]), max(0, y - sum_of_a + a[ind - 1]) + x - a[ind - 1]))


from bisect import bisect_left
from sys import stdin, gettrace
if gettrace():

	def inputi():
		return input()
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def main():
	n = int(input())
	aa = [int(a) for a in input().split()]
	m = int(input())
	dd = [[int(a) for a in input().split()] for _ in range(m)]
	aa.sort()
	tp = sum(aa)
	for (x, y) in dd:
		i = bisect_left(aa, x)
		if i == n:
			print(x - aa[n - 1] + max(0, y - tp + aa[n - 1]))
		elif i == 0:
			print(max(0, y - tp + aa[0]))
		else:
			print(min(x - aa[i - 1] + max(0, y - tp + aa[i - 1]), max(0, y - tp + aa[i])))
main()


import bisect
import sys
input = sys.stdin.readline

def find(a, n, x):
	i = bisect.bisect_right(a, x)
	return (a[max(0, i - 1)], a[min(n - 1, i)])
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
total_strength = sum(a)
m = int(input())
for _ in range(m):
	(x, y) = map(int, input().split())
	if total_strength <= y:
		coins = max(0, x - a[0]) + (y - (total_strength - a[0]))
	elif a[-1] <= x:
		coins = x - a[-1] + max(0, y - (total_strength - a[-1]))
	else:
		(slayer_strength_1, slayer_strength_2) = find(a, n, x)
		coins_1 = max(0, x - slayer_strength_1)
		coins_1 += max(0, y - (total_strength - slayer_strength_1))
		coins_2 = max(0, x - slayer_strength_2)
		coins_2 += max(0, y - (total_strength - slayer_strength_2))
		coins = min(coins_1, coins_2)
	print(coins)


from bisect import bisect_left as bl
n = int(input())
a = list(map(int, input().split()))
m = int(input())
d = []
for _ in range(m):
	d.append([int(x) for x in input().split()])
a.sort()
ts = sum(a)
for i in range(m):
	c = 0
	hi = bl(a, d[i][0])
	if hi == n:
		hi = n - 1
	cl = d[i][1] - ts + a[hi]
	h = d[i][0] - a[hi]
	c = h * (h > 0) + cl * (cl > 0)
	if hi > 0:
		cl = d[i][1] - ts + a[hi - 1]
		h = d[i][0] - a[hi - 1]
		cn = h * (h > 0) + cl * (cl > 0)
		print(min(c, cn))
		continue
	print(c)


from __future__ import division, print_function
import heapq
import os
import copy
import sys
from io import BytesIO, IOBase
from typing import Counter, DefaultDict
import bisect
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def main():
	n = int(input())
	a = list(map(int, input().split()))
	sm = sum(a)
	a.sort()
	q = int(input())
	while q:
		cost_pre = 0
		cost_post = 0
		(df, at) = map(int, input().split())
		ind = bisect.bisect_left(a, df)
		if ind == n:
			cost_pre += max(df - a[ind - 1], 0)
			cost_pre += max(at - (sm - a[ind - 1]), 0)
			print(cost_pre)
		else:
			cost_pre += max(df - a[ind - 1], 0)
			cost_pre += max(at - (sm - a[ind - 1]), 0)
			cost_post += max(df - a[ind], 0)
			cost_post += max(at - (sm - a[ind]), 0)
			print(min(cost_pre, cost_post))
		q -= 1
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import bisect
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')
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
a = list(set(a))
a.sort()

def solve():
	(x, y) = map(int, input().split())
	idx = bisect.bisect_left(a, x)
	hero1 = a[idx] if idx < len(a) else -float('inf')
	hero2 = a[idx - 1] if idx >= 1 else -float('inf')
	case1 = max(x - hero1, 0) + max(y - s + hero1, 0)
	case2 = max(x - hero2, 0) + max(y - s + hero2, 0)
	print(min(case1, case2))
for _ in range(int(input())):
	solve()


from sys import stdin
input = stdin.readline
from bisect import bisect_left, bisect_right
n = int(input())
heroes = list(map(int, input().split()))
heroes = sorted(heroes)
(d, total) = (int(input()), sum(heroes))
seen = {}
for _ in range(d):
	(attack, defense) = map(int, input().split())
	if attack in seen:
		i = seen[attack]
	else:
		i = bisect_left(heroes, attack)
		seen[attack] = i
	if i == n:
		print(attack - heroes[-1] + max(0, defense - total + heroes[-1]))
	elif i == 0:
		print(max(0, defense - total + heroes[0]))
	else:
		val1 = max(0, defense - total + heroes[i])
		val2 = attack - heroes[i - 1] + max(0, defense - total + heroes[i - 1])
		print(min(val1, val2))


import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import *
from collections import defaultdict, deque, Counter
import math, string
from heapq import *
from operator import add
from itertools import accumulate
BUFSIZE = 8192
sys.setrecursionlimit(10 ** 5)

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')
inf = float('inf')
en = lambda x: list(enumerate(x))
ceil_ = lambda a, b: (a + b - 1) // b
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
n = ii()
arr = rr()
arr.sort()
s = sum(arr)
m = ii()

def ok(arr, pos):
	global s
	c = 0
	c += max(0, i - arr[pos])
	x = s - arr[pos]
	c += max(0, j - x)
	return c
for _ in ' ' * m:
	(i, j) = r()
	c = inf
	pos = bisect_left(arr, i)
	a = max(0, pos - 1)
	c = min(c, ok(arr, a))
	a = min(pos, n - 1)
	c = min(c, ok(arr, a))
	a = min(pos + 1, n - 1)
	c = min(c, ok(arr, a))
	print(c)


import sys
input = sys.stdin.readline
import bisect
n = int(input())
A = list(map(int, input().split()))
m = int(input())
A.sort()
SUM = sum(A)
MAX = max(A)
for i in range(m):
	(x, y) = map(int, input().split())
	ANS = 0
	if x >= MAX:
		ANS += x - MAX
		S = SUM - MAX
		if S >= y:
			print(ANS)
		else:
			print(ANS + (y - S))
		continue
	k = bisect.bisect(A, x)
	u = A[k]
	S = SUM - u
	ANS = max(y - S, 0)
	if k == 0:
		print(ANS)
		continue
	else:
		u = A[k - 1]
		ANS2 = x - u
		S = SUM - u
		ANS2 += max(y - S, 0)
		print(min(ANS, ANS2))


from bisect import *
import sys
inf = float('inf')
ip = sys.stdin.readline

def ipl():
	return list(map(int, ip().split()))

def ipn():
	return int(ip())

def ipf():
	return float(ip())

def solve():
	n = ipn()
	a = ipl()
	a.sort()
	s = sum(a)
	for _ in range(ipn()):
		(x, y) = ipl()
		i = bisect_right(a, x)
		r = inf
		if i < n:
			r = min(r, abs(min(a[i] - x, 0)) + abs(min(s - a[i] - y, 0)))
		if i - 1 >= 0:
			r = min(r, abs(min(a[i - 1] - x, 0)) + abs(min(s - a[i - 1] - y, 0)))
		print(r)
t = 1
for _ in range(t):
	solve()


import bisect
n = int(input())
A = [int(x) for x in input().split()]
A.sort()
s = sum(A)
R = []
for i in range(int(input())):
	ans = 10 ** 20
	(x, y) = map(int, input().split())
	p = bisect.bisect_left(A, x)
	if p == 0:
		ans = min(ans, max(0, y + A[p] - s))
	elif p == len(A):
		ans = min(ans, x - A[p - 1] + max(0, y + A[p - 1] - s))
	else:
		ans = min(ans, max(0, y + A[p] - s))
		ans = min(ans, x - A[p - 1] + max(0, y + A[p - 1] - s))
	R.append(str(ans))
print('\n'.join(R))


from bisect import bisect

def read_stuff():
	n = int(input())
	strength = list(map(int, input().strip().split()))[:n]
	total_strength = sum(strength)
	strength = sorted(strength)
	m = int(input())
	dragons = []
	for i in range(m):
		row = []
		(x, y) = map(int, input().strip().split())
		row.append(x)
		row.append(y)
		dragons.append(row)
	for i in range(m):
		coins = 0
		x = dragons[i][0]
		y = dragons[i][1]
		bis = bisect(strength, x)
		before_x = -1
		before_x_diff = -1
		after_x = -1
		after_x_diff = -1
		if bis != 0:
			before_x = strength[bis - 1]
			before_x_diff = x - before_x
		if bis != len(strength):
			after_x = strength[bis]
			after_x_diff = after_x - x
		bef = 0
		if before_x < x:
			bef += before_x_diff
		if total_strength - before_x < y:
			bef += y - (total_strength - before_x)
		aft = 0
		if after_x > x:
			if total_strength - after_x < y:
				aft += y - (total_strength - after_x)
		if before_x == -1:
			if after_x != -1:
				print(aft)
			else:
				print('WTF')
		elif after_x == -1:
			print(bef)
		else:
			print(min(bef, aft))
read_stuff()


import bisect
import heapq
import math
import collections
import sys
import copy
from functools import reduce
import decimal
from io import BytesIO, IOBase
import os
import itertools
import functools
from types import GeneratorType
sys.setrecursionlimit(10 ** 9)
decimal.getcontext().rounding = decimal.ROUND_HALF_UP
graphDict = collections.defaultdict
queue = collections.deque

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		to = f(*args, **kwargs)
		if stack:
			return to
		else:
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						return to
					to = stack[-1].send(to)
	return wrappedfunc

class Graphs:

	def __init__(self):
		self.graph = graphDict(set)

	def add_edge(self, u, v):
		self.graph[u].add(v)
		self.graph[v].add(u)

	def dfs_utility(self, nodes, visited_nodes):
		visited_nodes.add(nodes)
		for neighbour in self.graph[nodes]:
			if neighbour not in visited_nodes:
				self.dfs_utility(neighbour, visited_nodes)

	def dfs(self, node):
		Visited = set()
		self.dfs_utility(i, Visited)

	def bfs(self, node, f_node):
		count = float('inf')
		visited = set()
		level = 0
		if node not in visited:
			queue.append([node, level])
			visited.add(node)
		flag = 0
		while queue:
			parent = queue.popleft()
			if parent[0] == f_node:
				flag = 1
				count = min(count, parent[1])
			level = parent[1] + 1
			for item in self.graph[parent[0]]:
				if item not in visited:
					queue.append([item, level])
					visited.add(item)
		return count if flag else -1

class Tree:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

def inorder(node, lis):
	if node:
		inorder(node.left, lis)
		lis.append(node.data)
		inorder(node.right, lis)
	return lis

def leaf_node_sum(root):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return root.data
	return leaf_node_sum(root.left) + leaf_node_sum(root.right)

def hight(root):
	if root is None:
		return -1
	if root.left is None and root.right is None:
		return 0
	return max(hight(root.left), hight(root.right)) + 1

class UF:

	def __init__(self, N):
		self._id = list(range(N))
		self._count = N
		self._rank = [0] * N

	def find(self, p):
		id = self._id
		while p != id[p]:
			p = id[p]
		return p

	def count(self):
		return self._count

	def connected(self, p, q):
		return self.find(p) == self.find(q)

	def union(self, p, q):
		id = self._id
		rank = self._rank
		i = self.find(p)
		j = self.find(q)
		if i == j:
			return
		self._count -= 1
		if rank[i] < rank[j]:
			id[i] = j
		elif rank[i] > rank[j]:
			id[j] = i
		else:
			id[j] = i
			rank[i] += 1

	def add_roads(self):
		return set(self._id)

	def __str__(self):
		return ' '.join([str(x) for x in self._id])

	def __repr__(self):
		return 'UF(' + str(self) + ')'

def rounding(n):
	return int(decimal.Decimal(f'{n}').to_integral_value())

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0), []))

def p_sum(array):
	return list(itertools.accumulate(array))

def diophantine(a: int, b: int, c: int):
	(d, x, y) = extended_gcd(a, b)
	r = c // d
	return (r * x, r * y)

@bootstrap
def extended_gcd(a: int, b: int):
	if b == 0:
		(d, x, y) = (a, 1, 0)
	else:
		(d, p, q) = (yield extended_gcd(b, a % b))
		x = q
		y = p - q * (a // b)
	yield (d, x, y)
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, **kwargs):
		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))

def inp():
	return sys.stdin.readline().strip()

def map_inp(v_type):
	return map(v_type, inp().split())

def list_inp(v_type):
	return list(map_inp(v_type))
n = int(inp())
arr = list_inp(int)
arr.sort()
pre = [0] + p_sum(arr)
m = int(inp())
for i in range(m):
	ans = 0
	(x, y) = map_inp(int)
	temp = bisect.bisect_right(arr, x)
	if temp == n:
		ans += x - arr[temp - 1]
		if y > pre[n] - arr[temp - 1]:
			ans += y - (pre[n] - arr[temp - 1])
		print(ans)
	elif temp == 0:
		if pre[n] - arr[0] >= y:
			print(0)
		else:
			print(y - (pre[n] - arr[0]))
	elif pre[n] - arr[temp] >= y:
		print(0)
	else:
		q = x - arr[temp - 1]
		if pre[n] - arr[temp - 1] >= y:
			q += 0
		else:
			q += y - (pre[n] - arr[temp - 1])
		w = y - (pre[n] - arr[temp])
		print(min(q, w))


import sys
input = sys.stdin.readline
from bisect import bisect_left as bl
from collections import defaultdict as dd, deque
L = lambda : list(map(int, input().split()))
n = L()[0]
A = L()
A.sort()
A = [0] + A
sm = sum(A)
B = [sm - A[i] for i in range(n + 1)]
d = {}
m = L()[0]
ans1 = deque()
for j in range(m):
	(x, y) = L()
	z = d.get(x, bl(A, x))
	d[x] = z
	ans = []
	for i in range(max(1, z - 1), min(n + 1, z + 1)):
		ans.append(max(x - A[i], 0) + max(y - B[i], 0))
	ans1.append(str(min(ans)))
print('\n'.join(ans1))


import sys
read = lambda : sys.stdin.readline()
from bisect import bisect_left
n = int(read())
heroes = list(map(int, read().split()))
heroes.sort()
totalStrength = sum(heroes)
m = int(read())
for _ in range(m):
	(defense, attack) = map(int, read().split())
	ans = 10 ** 30
	idx = bisect_left(heroes, defense)
	if idx == 0:
		ans = min(ans, max(attack - (totalStrength - heroes[idx]), 0))
	elif idx == n:
		ans = min(ans, defense - heroes[idx - 1] + max(attack - (totalStrength - heroes[idx - 1]), 0))
	else:
		ans = min(ans, max(attack - (totalStrength - heroes[idx]), 0), defense - heroes[idx - 1] + max(attack - (totalStrength - heroes[idx - 1]), 0))
	print(ans)


import sys
input = sys.stdin.readline
import bisect
heroes = int(input())
heroes_strength = list(map(int, input().split()))
number_dragons = int(input())
heroes_strength.sort()
all_strength = sum(heroes_strength)
max_strength = max(heroes_strength)
for i in range(number_dragons):
	(dragon_defense, dragon_attack) = map(int, input().split())
	coins = 0
	if dragon_defense >= max_strength:
		coins += dragon_defense - max_strength
		remaining_strength = all_strength - max_strength
		if remaining_strength >= dragon_attack:
			print(coins)
		else:
			print(coins + (dragon_attack - remaining_strength))
		continue
	k = bisect.bisect(heroes_strength, dragon_defense)
	required_strength = heroes_strength[k]
	remaining_strength = all_strength - required_strength
	coins = max(dragon_attack - remaining_strength, 0)
	if k == 0:
		print(coins)
		continue
	else:
		required_strength = heroes_strength[k - 1]
		coins2 = dragon_defense - required_strength
		remaining_strength = all_strength - required_strength
		coins2 += max(dragon_attack - remaining_strength, 0)
		print(min(coins, coins2))


import sys
from math import factorial, gcd
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest, nsmallest
from itertools import groupby
from copy import deepcopy
MOD = 10 ** 9 + 7
INF = float('inf')
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
rl = lambda : list(map(int, input().split()))
rs = lambda : sys.stdin.readline().strip()
n = int(input())
A = sorted(rl())
m = int(input())
total = sum(A)
for _ in range(m):
	(de, att) = rl()
	if de <= A[0]:
		res = max(0, att - (total - A[0]))
		print(res)
		continue
	if de >= A[-1]:
		res = de - A[-1] + max(0, att - (total - A[-1]))
		print(res)
		continue
	idx = bisect_right(A, de)
	res = max(0, de - A[idx - 1])
	res += max(0, att - total + A[idx - 1])
	cur = max(0, de - A[idx])
	cur += max(0, att - total + A[idx])
	print(min(res, cur))


import sys
from bisect import bisect_left
input = sys.stdin.readline
n = int(input())
hero = list(map(int, input().split()))
hero.sort()
total = sum(hero)
dragon = int(input())
for i in range(dragon):
	(x, y) = map(int, input().split())
	idx = bisect_left(hero, x)
	v = 0
	if idx == n:
		v = x - hero[-1] + max(0, y - (total - hero[-1]))
	elif idx == 0 or hero[idx] == x:
		v = max(0, y - (total - hero[idx]))
	else:
		(v1, v2) = (hero[idx - 1], hero[idx])
		v = min(max(x - v1, 0) + max(0, y - (total - v1)), max(x - v2, 0) + max(0, y - (total - v2)))
	print(v)


import os
import sys
from io import BytesIO, IOBase
import math as mt
import itertools as it
import operator as op
import bisect as bs
import heapq as hp
from functools import reduce
from io import BytesIO, IOBase
from collections import deque, defaultdict, OrderedDict, Counter, ChainMap, _chain
(maxx, localsys, mod) = (1 << 60, 0, int(1000000000.0 + 7))

def nCr(n, r):
	return reduce(op.mul, range(n - r + 1, n + 1), 1) // mt.factorial(r)

def ceil(a, b):
	return (a + b - 1) // b

def lcm(a, b):
	return a * b // mt.gcd(a, b)
gcdm = lambda *args: reduce(mt.gcd, args, 0)

def lcm(a, b):
	return a * b // mt.gcd(a, b)
lcmm = lambda *args: reduce(lcm, args, 1)
_str = str
str = lambda x=b'': x if type(x) is bytes else _str(x).encode()
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))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return map(int, input().split())
INF = 10 ** 40
import sys
import pprint
import logging
from logging import getLogger
import array

def input():
	return sys.stdin.readline().rstrip('\r\n')

def maps():
	return [int(i) for i in input().split()]
logging.basicConfig(format='%(message)s', level=logging.WARNING)
logger = getLogger(__name__)
logger.setLevel(logging.INFO)

def debug(msg, *args):
	logger.info(f'{msg}={pprint.pformat(args)}')

def search(arr, key):
	(l, h) = (0, len(arr) - 1)
	idx = n - 1
	while l <= h:
		m = l + h >> 1
		if arr[m][0] <= key:
			l = m + 1
		else:
			idx = m
			h = m - 1
	return idx
from itertools import accumulate
(n,) = maps()
a = [*maps()]
(m,) = maps()
arr = [[*maps()] for _ in range(m)]
tot = sum(a)
A = []
a.sort()
for i in range(n):
	A.append((tot - a[i], a[i]))
A.sort(key=lambda x: (x[0], x[1]))
ans = [0] * m
ii = 0
for (defense, attack) in arr:
	idx = search(A, attack)
	if attack <= A[idx][0] and defense <= A[idx][1]:
		ans[ii] = 0
	else:
		mx = defense + attack
		(t1, t2, t3) = (0, 0, 0)
		if attack > A[idx][0]:
			t1 += attack - A[idx][0]
		if defense > A[idx][1]:
			t1 += defense - A[idx][1]
		if idx - 1 >= 0:
			if attack > A[idx - 1][0]:
				t2 += attack - A[idx - 1][0]
			if defense > A[idx - 1][1]:
				t2 += defense - A[idx - 1][1]
		else:
			t2 = INF
		if idx + 1 < n:
			if attack > A[idx + 1][0]:
				t3 += attack - A[idx + 1][0]
			if defense > A[idx + 1][1]:
				t3 += defense - A[idx + 1][1]
		else:
			t3 = INF
		mx = min(mx, t3, t2, t1)
		ans[ii] = mx
	ii += 1
print(*ans, sep='\n')


from sys import stdin
from bisect import bisect_left
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
mod = 10 ** 9 + 7
n = rn()
a = rl()
a.sort()
s = sum(a)
m = rn()
for _ in range(m):
	(de, atk) = rns()
	j = bisect_left(a, de)
	if j == n:
		j -= 1
	ans = []
	if j > 0:
		ans.append(max(0, de - a[j - 1]) + max(0, atk - (s - a[j - 1])))
	ans.append(max(0, de - a[j]) + max(0, atk - (s - a[j])))
	print(min(ans))


import os, sys, bisect
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')
from math import ceil
mod = 10 ** 9 + 7
for _ in range(1):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	prefix = [0] * n
	suffix = [0] * n
	final = []
	for i in range(n):
		prefix[i] = prefix[i - 1] + a[i] if i != 0 else a[i]
	for i in range(n - 1, -1, -1):
		suffix[i] = suffix[i + 1] + a[i] if i != n - 1 else a[i]
	for i in range(int(input())):
		(health, damage) = map(int, input().split())
		if health <= prefix[0]:
			if prefix[-1] - prefix[0] >= damage:
				ans = 0
			else:
				ans = abs(damage - (prefix[-1] - prefix[0]))
		elif health > suffix[-1]:
			ans = health - suffix[-1]
			if prefix[-2] < damage:
				ans += damage - prefix[-2]
		else:
			pos = bisect.bisect_left(a, health)
			ans = health - a[pos - 1]
			pos = pos - 1
			if pos > 0:
				total = prefix[pos - 1] + suffix[pos + 1]
			else:
				total = suffix[pos + 1]
			if total < damage:
				ans += damage - total
			pos += 1
			if pos < n - 1:
				total = prefix[pos - 1] + suffix[pos + 1]
			else:
				total = prefix[pos - 1]
			temp = float('inf')
			if total < damage:
				temp = damage - total
			else:
				temp = 0
			ans = min(ans, temp)
		final.append(ans)
	for i in final:
		print(i)


import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	net = sum(A)
	m = int(input())
	dragon = []
	for i in range(m):
		(x, y) = map(int, input().split())
		dragon.append([x, y])
	for i in dragon:
		(x, y) = i
		e = bisect.bisect_left(A, x)
		if e == 0:
			add_to_attack = 0
			rem = net - A[0]
			add_to_defend = max(0, y - rem)
		elif e == n:
			add_to_attack = x - A[n - 1]
			rem = net - A[n - 1]
			add_to_defend = max(0, y - rem)
		else:
			one = x - A[e - 1] + max(0, y - (net - A[e - 1]))
			two = 0 + max(0, y - (net - A[e]))
			print(min(one, two))
			continue
		print(add_to_attack + add_to_defend)
t = 1
while t != 0:
	solve()
	t -= 1


from sys import stdin
import bisect
n = int(stdin.readline())
a = sorted(map(int, stdin.readline().split()))
s = sum(a)
for _ in range(int(stdin.readline())):
	(x, y) = list(map(int, stdin.readline().split()))
	i = bisect.bisect(a, x)
	if i == n:
		print(max(0, y - (s - a[i - 1])) + max(0, x - a[i - 1]))
	elif a[i] == x or i == 0:
		print(max(0, y - (s - a[i])))
	elif i > 0:
		res1 = max(0, y - (s - a[i]))
		res2 = max(0, y - (s - a[i - 1])) + x - a[i - 1]
		print(min(res1, res2))


import bisect
from sys import stdin
input = stdin.readline
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
s = sum(arr)
m = int(input())
for i in range(m):
	(d, a) = map(int, input().split())
	index = bisect.bisect_left(arr, d)
	if index == len(arr):
		print(d - arr[-1] + max(0, a - (s - arr[-1])))
	elif index <= 0:
		print(max(0, a - (s - arr[0])))
	else:
		print(min(max(0, a - (s - arr[index])), max(0, d - arr[index - 1] + max(0, a - (s - arr[index - 1])))))


from collections import deque, Counter
from collections import defaultdict as dfd
from bisect import bisect, bisect_left
from math import sqrt, gcd, ceil, factorial, log2
from heapq import heapify, heappush, heappop
MOD = 10 ** 9 + 7
inf = float('inf')
ans_ = []

def nin():
	return int(input())

def ninf():
	return int(file.readline())

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

def stf():
	return file.readline().strip()

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

def readf():
	return list(map(int, file.readline().strip().split()))

def readfl():
	return list(map(float, input().strip().split()))

def readffl():
	return list(map(float, file.readline().strip().split()))

def solve():
	n = nin()
	arr = read()
	m = nin()
	arr.sort()
	s = sum(arr)
	for i in range(m):
		(x, y) = read()
		ind = bisect(arr, x)
		ind2 = bisect(arr, x - 1)
		if ind != 0 and arr[ind - 1] == x or ind == n:
			ind -= 1
		if ind2 != 0 and arr[ind2 - 1] < x or ind2 == n:
			ind2 -= 1
		a = max(0, x - arr[ind]) + max(0, y - (s - arr[ind]))
		b = max(0, x - arr[ind2]) + max(0, y - (s - arr[ind2]))
		ans_.append(min(a, b))
solve()
for i in ans_:
	print(i)


import bisect
import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
m = int(input())
a = sorted(a)
sum_a = sum(a)
INF = 2 * 10 ** 18
for _ in range(m):
	(x, y) = map(int, input().split())
	idx = bisect.bisect_left(a, x)
	res = INF
	if idx < n:
		nokori = sum_a - a[idx]
		res = min(max(y - nokori, 0), res)
	if idx - 1 >= 0:
		nokori = sum_a - a[idx - 1]
		res = min(max(y - nokori, 0) + (x - a[idx - 1]), res)
	print(res)


import sys
from bisect import *
input = sys.stdin.readline
n = int(input())
h = sorted(list(map(int, input().split())))
m = int(input())
su = sum(h)
for i in range(m):
	ans = 0
	(k, d) = map(int, input().split())
	f = bisect_left(h, k)
	if f > n - 1:
		f -= 1
	u = 0
	o = 0
	u += max(0, k - h[f]) + max(0, d - (su - h[f]))
	o += max(0, k - h[f - 1]) + max(0, d - (su - h[f - 1]))
	ans = min(u, o)
	print(ans)


from sys import stdin
from bisect import bisect_left
input = stdin.readline

def SlayD(n, Power, Dragon, E):
	key = bisect_left(Power, Dragon[0])
	key = max(0, min(n - 1, key))
	CoinA = max(0, Dragon[1] - (E - Power[key])) + max(0, Dragon[0] - Power[key])
	CoinB = max(0, Dragon[1] - (E - Power[key - 1])) + max(0, Dragon[0] - Power[key - 1])
	Coin = min(CoinA, CoinB)
	return Coin
num_of_hero = int(input())
I = [int(x) for x in input().split()]
I.sort()
E = sum(I)
num_of_d = int(input())
for i in range(num_of_d):
	(x, y) = map(int, input().split())
	print(SlayD(num_of_hero, I, [x, y], E))


import math
import heapq
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
H = 1000000000 + 7
n = I()
l = L()
l.sort()
s = sum(l)
m = I()
for i in range(m):
	(a, b) = M()
	c = 0
	i = bisect_left(l, a)
	if i == n:
		print(a - l[-1] + max(0, b - s + l[-1]))
	elif i == 0:
		print(max(0, b - s + l[i]))
	elif abs(l[i - 1] - a) + max(0, b - s + l[i - 1]) < max(0, b - s + l[i]):
		print(abs(l[i - 1] - a) + max(0, b - s + l[i - 1]))
	else:
		print(max(0, b - s + l[i]))


import sys
import os
from math import ceil, floor, sqrt, gcd, factorial, log, log2
from io import BytesIO, IOBase
from collections import Counter
from itertools import permutations, combinations
from bisect import bisect
from functools import reduce
inf = int(10000000000.0)
BUFSIZE = 8192
inp = lambda : int(input())
mp = lambda : map(int, input().split())
lst = lambda : list(map(int, input().split()))

def main():
	n = inp()
	a = lst()
	a.sort()
	s = sum(a)
	m = inp()
	l = []
	for i in range(m):
		(x, y) = mp()
		c = 0
		c1 = 0
		if x >= a[-1]:
			c += x - a[-1]
			if s - a[-1] < y:
				c += y - (s - a[-1])
			print(c)
		else:
			j = bisect(a, x)
			if s - a[j - 1] < y:
				c += y - (s - a[j - 1])
			if a[j - 1] < x:
				c += x - a[j - 1]
			if s - a[j] < y:
				c1 += y - (s - a[j])
			print(min(c, c1))

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
from collections import defaultdict
from bisect import bisect_left
from sys import stdin
input = stdin.readline
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
a.sort()
m = int(input())
for i in range(m):
	(x, y) = map(int, input().split())
	index = bisect_left(a, x)
	if index != 0:
		index -= 1
	f_ans = 0
	ans = 0
	if a[index] < x:
		ans += x - a[index]
	new_s = s - a[index]
	if new_s < y:
		ans += y - new_s
	if index != len(a) - 1:
		index += 1
	f_ans = ans
	ans = 0
	if a[index] < x:
		ans += x - a[index]
	new_s = s - a[index]
	if new_s < y:
		ans += y - new_s
	f_ans = min(f_ans, ans)
	print(f_ans)


import traceback
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 = IOWrapper(sys.stdin)
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
from collections import defaultdict as dfd, defaultdict, Counter, deque
from functools import lru_cache
from itertools import accumulate
from heapq import *
from bisect import *

def geti():
	return int(input())

def gets():
	return input()

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

def getsl():
	return input().split()

def getinps(s):
	inps = s.split()
	m = {'i': geti, 's': gets, 'il': getil, 'sl': getsl}
	if len(inps) == 1:
		return m[s]()
	return [m[k]() for k in inps]

def get2d(nrows, ncols, n=0):
	return [[n] * ncols for r in range(nrows)]

def get_acc(a):
	return list(accumulate(a))

def get_ncr(n, r, mod=10 ** 9 + 7):
	num = den = 1
	r = min(r, n - r)
	for i in range(r):
		num = num * (n - i) % mod
		den = den * (i + 1) % mod
	return num * pow(den, mod - 2, mod) % mod

def get_nc2(n):
	return n * (n - 1) // 2

def get_npr(n, r):
	if n < r:
		return 0
	return math.factorial(n) // math.factorial(r)

def put(a):
	return ' '.join(map(str, a))
ALPHABETS = 'abcdefghijklmnopqrstuvwxyz'
VOWELS = 'aeiou'
CONSONANTS = 'bcdfghjklmnpqrstvwxyz'
inf = float('inf')
mod = 10 ** 9 + 7

class Solution:

	def main(self):
		(N,) = getil()
		a = getil()
		b = []
		a.sort()
		tot = sum(a)

		def solve(d, p):
			y = bisect_left(a, d)
			ans = inf
			for x in [y, y - 1]:
				if not 0 <= x < N:
					continue
				ans = min(ans, max(0, d - a[x]) + max(0, p - (tot - a[x])))
			return ans
		for _ in range(geti()):
			(x, y) = getil()
			print(solve(x, y))
try:
	Sol = Solution()
	ans = Sol.main()
except Exception as e:
	print(e)
	traceback.print_exc()


import sys
import bisect
input = sys.stdin.readline

def fun(x, y, sumi):
	idx = bisect.bisect_left(arr, x)
	if idx == len(arr):
		idx = len(arr) - 1
	attack = max(x - arr[idx], 0)
	defense = max(y - sumi + arr[idx], 0)
	ans = attack + defense
	if idx > 0:
		idx -= 1
		attack = max(x - arr[idx], 0)
		defense = max(y - sumi + arr[idx], 0)
		ans = min(ans, attack + defense)
	return ans
n = int(input())
arr = list(map(int, input().split()))
m = int(input())
arr.sort()
sumi = sum(arr)
for _ in range(m):
	(x, y) = map(int, input().split())
	print(fun(x, y, sumi))


import bisect
import sys
input = sys.stdin.readline
n = int(input())
hero = list(map(int, input().split()))
m = int(input())
hero.sort()
c = sum(hero)
for i in range(m):
	(x, y) = map(int, input().split())
	r = bisect.bisect_left(hero, x)
	if r == n:
		ans = max(0, x - hero[n - 1])
		ans += max(0, y - (c - hero[n - 1]))
	elif r == 0:
		ans = max(0, x - hero[0])
		ans += max(0, y - (c - hero[0]))
	else:
		ans1 = max(0, x - hero[r])
		ans1 += max(0, y - (c - hero[r]))
		ans2 = max(0, x - hero[r - 1])
		ans2 += max(0, y - (c - hero[r - 1]))
		ans = min(ans1, ans2)
	print(ans)


from string import ascii_lowercase
from decimal import Decimal
from random import randrange, choice, randint, shuffle
import time
from heapq import heappop, heappush, heapify
from copy import copy
from bisect import bisect_right, bisect_left
from sys import stdin
from functools import reduce
from math import sqrt, gcd, pi, factorial, ceil, floor, sin
from itertools import permutations
from collections import defaultdict, deque, Counter
import sys
input = sys.stdin.readline
MAX = 10 ** 19

def solve(n, a, x, y, s):
	index = bisect_left(a, x)
	ret = MAX
	if index > 0:
		attacker = a[index - 1]
		ret = min(ret, max(x - attacker, 0) + max(y - (s - attacker), 0))
	if index < n - 1:
		attacker = a[index]
		ret = min(ret, max(x - attacker, 0) + max(y - (s - attacker), 0))
	return ret
n = int(input())
a = sorted(list(map(int, input().split())))
m = int(input())
s = sum(a)
ans = [0 for _ in range(m)]
for i in range(m):
	(x, y) = map(int, input().split())
	ans[i] = solve(n, a, x, y, s)
for a in ans:
	print(a)


import math, sys
from collections import Counter, defaultdict, deque
from heapq import heapify, heappush, heappop
from bisect import bisect_left
INF = float('inf')

def solve():
	n = int(input())
	a = sorted(list(map(int, input().split())))
	b = []
	total = sum(a)
	m = int(input())
	for _ in range(m):
		(x, y) = map(int, input().split())
		i = bisect_left(a, x)
		coin = INF
		if i > 0:
			coin = min(coin, x - a[i - 1] + max(0, y - total + a[i - 1]))
		if i < n:
			coin = min(coin, max(0, y - total + a[i]))
		print(coin)

def input():
	return sys.stdin.readline().rstrip('\n').strip()

def print(*args, sep=' ', end='\n'):
	first = True
	for arg in args:
		if not first:
			sys.stdout.write(sep)
		sys.stdout.write(str(arg))
		first = False
	sys.stdout.write(end)
ts = 1
for t in range(1, ts + 1):
	solve()


from bisect import bisect_left
from sys import stdin
input = stdin.readline
n = int(input())
a = [int(x) for x in input().split()] + [10 ** 17]
a.sort()
s = sum(a[:-1])
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	l = bisect_left(a, x)
	print(min(max(0, x - a[l - 1]) + max(0, y - s + a[l - 1]), max(0, x - a[l]) + max(0, y - s + a[l])))


from sys import stdin, stdout
input = stdin.buffer.readline
import bisect

def f(ind):
	ind = min(ind, n - 1)
	if ind < 0:
		return 0
	return pre[ind]
t = 1
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr = sorted(arr)
	pre = [0 for i in range(n)]
	pre[0] = arr[0]
	for i in range(1, n):
		pre[i] = arr[i] + pre[i - 1]
	q = int(input())
	for i in range(q):
		(a, b) = map(int, input().split())
		ind = bisect.bisect(arr, a)
		ans = float('inf')
		if ind != 0:
			left = f(ind - 2) + f(n - 1) - f(ind - 1)
			ans = max(b - left, 0) + max(0, a - arr[ind - 1])
		if ind != n:
			left = f(ind - 1) + f(n - 1) - f(ind)
			ans = min(ans, max(b - left, 0) + max(0, a - arr[ind]))
		ind2 = bisect.bisect_left(arr, a) - 1
		if ind2 >= 0:
			left = f(ind2 - 1) + f(n - 1) - f(ind2)
			temp = max(0, a - arr[ind2]) + max(0, b - left)
			ans = min(ans, temp)
		stdout.write(str(ans) + '\n')


import bisect
import math
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()
m = int(input())
s = sum(a)
for _ in range(m):
	(x, y) = map(int, input().split())
	ans = 0
	index = bisect.bisect_left(a, x)
	ans = max(0, x - a[index - 1])
	ans += max(0, y - (s - a[index - 1]))
	ans2 = math.inf
	if index != n:
		ans2 = max(0, x - a[index])
		ans2 += max(0, y - (s - a[index]))
	print(min(ans, ans2))


from bisect import bisect_left
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()
sum_a = sum(a)
m = int(input())
for _ in range(m):
	(x, y) = map(int, input().split())
	idx = bisect_left(a, x)
	if idx == 0:
		res = max(y - (sum_a - a[idx]), 0)
	elif idx == len(a):
		res = max(y - (sum_a - a[idx - 1]), 0) + max(x - a[idx - 1], 0)
	else:
		res = min(max(y - (sum_a - a[idx - 1]), 0) + max(x - a[idx - 1], 0), max(y - (sum_a - a[idx]), 0))
	sys.stdout.write(str(res) + '\n')


from bisect import bisect_left
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
total = sum(a)
a.sort()
m = int(input())
for _ in range(m):
	(x, y) = map(int, input().split())
	pos = bisect_left(a, x)
	pos = max(0, min(n - 1, pos))
	ans1 = max(0, x - a[pos - 1]) + max(0, y - (total - a[pos - 1]))
	ans2 = max(0, x - a[pos]) + max(0, y - (total - a[pos]))
	print(min(ans1, ans2))


from bisect import bisect_right
from sys import stdin, stdout
input = stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
s = sum(a)
m = int(input())
for _ in range(m):
	(x, y) = list(map(int, input().split()))
	if x <= a[0]:
		total = max(y - (s - a[0]), 0)
	elif x >= a[n - 1]:
		total = x - a[n - 1] + max(y - (s - a[n - 1]), 0)
	else:
		i = bisect_right(a, x)
		total = min(max(x - a[i], 0) + max(y - (s - a[i]), 0), max(x - a[i - 1], 0) + max(y - (s - a[i - 1]), 0))
	print(total)


from bisect import *
import sys
input = sys.stdin.readline
n = int(input())
li = list(map(int, input().split()))
li.sort()
fullStrength = sum(li)
output = []
for _ in range(int(input())):
	(xi, yi) = map(int, input().split())
	left = min(n - 1, bisect_left(li, xi))
	val = 0
	if left > 0:
		leftone = left - 1
	else:
		leftone = left
	val = min(max(0, xi - li[left]) + max(0, yi - (fullStrength - li[left])), max(0, xi - li[leftone]) + max(0, yi - (fullStrength - li[leftone])))
	print(val)


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

def so():
	return int(input())

def st():
	return input()

def mj():
	return map(int, input().strip().split(' '))

def msj():
	return map(str, input().strip().split(' '))

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

def lebe():
	return list(map(int, input()))

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(1024000)
	thread = threading.Thread(target=main)
	thread.start()

def joro(L):
	return ''.join(map(str, L))

def cheems(c, d):
	a = 1
	while d != 0:
		if d % 2 == 1:
			a *= c
		c = c * c
		d = d // 2
	return a

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def npr(n, r):
	return factorial(n) // factorial(n - r) if n >= r else 0

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def tir(a, b, c):
	if 0 == c:
		return 1
	if len(a) <= b:
		return 0
	if c != -1:
		return tir(a, 1 + b, c + a[b]) or tir(a, b + 1, c - a[b]) or tir(a, 1 + b, c)
	else:
		return tir(a, 1 + b, a[b]) or tir(a, b + 1, -a[b]) or tir(a, 1 + b, -1)

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val, lb, ub):
	ans = -1
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = mid
			break
	return ans

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def wubu(m):
	import math as my
	d = 0
	while not m % 2:
		m = m // 2
		d = 1 + d
	for i in range(3, int(my.sqrt(m)) + 1, 2):
		while not m % i:
			m = m // i
			d = 1 + d
	return int(m > 1) + d

def pref(li):
	pref_sum = [0]
	for i in li:
		pref_sum.append(pref_sum[-1] + i)
	return pref_sum

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	li = []
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, len(prime)):
		if prime[p]:
			li.append(p)
	return li

def primefactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 2:
		factors.append(n)
	return factors

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def tr(n):
	return n * (n + 1) // 2

def bro(q, r, c):
	(bec, pot, h) = (0, 0, 0)
	ds = []
	bs = []
	es = []
	for i in range(c):
		while h < len(r) and r[h] <= q[i][0]:
			pot = 0
			ds.clear()
			bs.clear()
			h = 1 + h
	for i in range(c):
		ds.append(q[i][1])
		es.append(q[i][1])
	ds = list(set(ds))
	for i in ds:
		bs.append(es.count(i))
	print(bs)
	for i in range(c):
		if q[i][0] > r[h - 1]:
			bec = bec + pot - bs[i]
			pot = 1 + pot
	return bec

def main():
	import sys
	input = sys.stdin.readline
	import math as my
	import bisect as op
	p = so()
	L = sorted(le())
	q = so()
	opp = 0
	for i in L:
		opp = i + opp
	for i in range(q):
		KO = []
		(r, s) = mj()
		kt = op.bisect_left(L, r)
		jy = min(kt, p - 1)
		kt = max(jy, 0)
		fr = max(s + L[kt] - opp, 0) + max(0, r - L[kt])
		frr = max(0, r - L[kt - 1]) + max(-opp + L[kt - 1] + s, 0)
		KO.append(fr)
		KO.append(frr)
		print(min(KO))
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import bisect
from sys import stdin
input = stdin.readline
n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
capacity = sum(a)
m = int(input())
for i in range(m):
	(k, d) = map(int, input().split(' '))
	index = bisect.bisect_left(a, k)
	ans = 0
	if index == 0:
		defense = capacity - a[0]
		if defense < d:
			ans += d - defense
	elif index == n:
		ans += k - a[n - 1]
		defense = capacity - a[n - 1]
		if defense < d:
			ans += d - defense
	elif a[index - 1] == k:
		defense = capacity - a[index - 1]
		if defense < d:
			ans += d - defense
	else:
		defense1 = capacity - a[index - 1]
		kill1 = k - a[index - 1]
		sol1 = kill1
		if defense1 < d:
			sol1 += d - defense1
		defense2 = capacity - a[index]
		sol2 = 0
		if defense2 < d:
			sol2 += d - defense2
		ans = min(sol1, sol2)
	print(ans)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
A = list(map(int, input().split()))
A.sort()
s = sum(A)
m = int(input())
import bisect
for i in range(m):
	(x, y) = map(int, input().split())
	j = bisect.bisect_left(A, x)
	if j != n:
		if j != 0:
			a = A[j]
			ans1 = 0
			if s - a <= y:
				ans1 += y - (s - a)
			a = A[j - 1]
			ans2 = 0
			ans2 += x - a
			if s - a <= y:
				ans2 += y - (s - a)
			ans = min(ans1, ans2)
		else:
			a = A[j]
			ans1 = 0
			if s - a <= y:
				ans1 += y - (s - a)
			ans = ans1
		print(ans)
	else:
		a = A[-1]
		ans = x - A[-1]
		if s - a <= y:
			ans += y - (s - a)
		print(ans)


import math
from collections import Counter, deque
from math import *
from bisect import *
mod = 998244353

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	sm = sum(l)
	m = int(input())
	l2 = []
	for i in range(m):
		l2.append(map(int, input().split()))
	for i in range(m):
		(x, y) = l2[i]
		if x > l[-1]:
			ans = x - l[-1] + max(0, y - sm + l[-1])
		else:
			ind = bisect_left(l, x, 0, n)
			if l[ind] == x:
				ans = max(0, y - sm + l[ind])
			else:
				ans1 = max(0, x - l[ind]) + max(0, y - sm + l[ind])
				if ind != 0:
					ans2 = max(0, y - sm + l[ind - 1])
					ans2 += max(0, x - l[ind - 1])
					ans = min(ans1, ans2)
				else:
					ans = ans1
		print(ans)
t = 1
for _ in range(t):
	solve()


from bisect import bisect_left
from sys import stdin
input = stdin.readline
n = int(input())
a = [int(x) for x in input().split()] + [1000000000001]
a.sort()
ss = sum(a[:-1])
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	l = bisect_left(a, x)
	print(min(max(0, x - a[l - 1]) + max(0, y - ss + a[l - 1]), max(0, x - a[l]) + max(0, y - ss + a[l])))


import sys
import io
from io import BytesIO, IOBase
import os
import bisect
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')
INF = 10 ** 20

def solve(N, A, S, X, Y):
	k = bisect.bisect_left(A, X)
	cost1 = -1
	if k < N:
		cost1 = max(Y - (S - A[k]), 0)
	cost2 = -1
	if 0 < k:
		cost2 = X - A[k - 1] + max(Y - (S - A[k - 1]), 0)
	if cost1 == -1:
		return cost2
	elif cost2 == -1:
		return cost1
	elif cost1 < cost2:
		return cost1
	else:
		return cost2
N = int(input())
A = list(map(int, input().split()))
A.sort()
S = sum(A)
M = int(input())
for _ in range(M):
	(X, Y) = map(int, input().split())
	print(solve(N, A, S, X, Y))


import sys
import math
import collections
import bisect
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
r = sys.stdin.readline
N = int(r())
L = list(map(int, r().split()))
M = int(r())
L.sort()
S = sum(L)
for i in range(M):
	(a, b) = map(int, r().split())
	big = bisect.bisect_left(L, a)
	if big == N:
		ans = a - L[-1]
		if b > S - L[-1]:
			ans += b - (S - L[-1])
		print(ans)
		continue
	ans1 = 0
	if b > S - L[big]:
		ans1 += b - (S - L[big])
	if big != 0:
		ans2 = 0
		ans2 += a - L[big - 1]
		if b > S - L[big - 1]:
			ans2 += b - (S - L[big - 1])
		ans1 = min(ans1, ans2)
	print(ans1)


import sys
from bisect import bisect
input = sys.stdin.readline

def solve():
	n = int(input())
	(*a,) = map(int, input().split())
	a.sort()
	d = dict()
	for i in range(1, len(a)):
		if a[i] != a[i - 1]:
			d[a[i]] = a[i - 1]
	s = sum(a)
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		b = bisect(a, x - 1)
		if b == n:
			h = s - a[-1]
			print(x - a[-1] + max(y - h, 0))
		else:
			h = s - a[b]
			r = max(y - h, 0)
			if a[b] in d:
				v = d[a[b]]
				h = s - v
				r = min(r, x - v + max(y - h, 0))
			print(r)
solve()


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

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
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')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def choose(x):
	if x == -1 or x == n:
		return inf
	cur = tot - a[x]
	need = max(0, attack - cur)
	need += max(0, defence - a[x])
	return need
for _ in range(1):
	n = Int()
	a = array()
	tot = sum(a)
	a.sort()
	for q in range(Int()):
		(defence, attack) = value()
		ind = bisect_left(a, defence)
		cur = tot
		need = min(choose(ind), choose(ind - 1))
		print(need)


import sys, os, io
I = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(I())
a = list(map(int, I().split()))
m = int(I())
(x, y) = ([], [])
for _ in range(m):
	(_x, _y) = map(int, I().split())
	x.append(_x)
	y.append(_y)
sa = sum(a)
a.sort()
d2 = 1
while d2 < n:
	d2 *= 2
for dr in range(m):
	coins = x[dr] + y[dr]
	d = d2
	i = -1
	while d > 0:
		if i + d < n:
			if a[i + d] < x[dr]:
				i += d
		d //= 2
	if i >= 0:
		c = x[dr] - a[i]
		c += max(0, y[dr] - sa + a[i])
		coins = min(coins, c)
	i += 1
	if i < n:
		coins = min(coins, max(0, y[dr] - sa + a[i]))
	print(coins)


import os
import sys
from io import BytesIO, IOBase
from bisect import bisect_right, insort_right
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')
getint = lambda : int(sys.stdin.readline().rstrip('\r\n'))
getints = lambda : map(int, sys.stdin.readline().rstrip('\r\n').split())
lgetints = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
getstrs = lambda : map(str, sys.stdin.readline().rstrip('\r\n').split())

def prog_name():
	n = getint()
	l = lgetints()
	m = getint()
	l.sort()
	j = sum(l)
	for i in range(m):
		s = j
		coin1 = 0
		coin2 = 0
		coin = 0
		(x, y) = getints()
		ind = bisect_right(l, x)
		if ind == 0:
			s -= l[0]
			print(max(0, y - s))
		elif ind == n:
			s -= l[-1]
			coin += x - l[-1]
			if y <= s:
				print(coin)
			else:
				coin += y - s
				print(coin)
		else:
			if s - l[ind - 1] < y:
				coin1 += y - (s - l[ind - 1])
			if l[ind - 1] < x:
				coin1 += x - l[ind - 1]
			if s - l[ind] < y:
				coin2 += y - (s - l[ind])
			print(min(coin1, coin2))

def main():
	T = 1
	for unique in range(T):
		prog_name()
main()


import sys
input = sys.stdin.readline
import bisect
n = int(input())
w = sorted(map(int, input().split()))
ss = sum(w)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c1 = bisect.bisect_right(w, a)
	if c1 == 0 or w[c1 - 1] == a:
		s = ss
		s -= a if w[c1 - 1] == a else w[0]
		print(b - s if b > s else 0)
	elif c1 == n:
		s = ss
		s -= w[-1]
		c = a - w[-1]
		print(b - s + c if b > s else c)
	else:
		s1 = ss - w[c1]
		s2 = ss - w[c1 - 1]
		c = a - w[c1 - 1]
		print(min(b - s1 if b > s1 else 0, b - s2 + c if b > s2 else c))


from bisect import bisect_left

def mgc(a, n, b, m):
	s = sum(a)
	for dra in b:
		(x, y) = (dra[0], dra[1])
		if x > a[-1]:
			ans = x - a[-1] + max(0, y - s + a[-1])
		else:
			ind = bisect_left(a, x, 0, n)
			if a[ind] == x:
				ans = max(0, y - s + a[ind])
			else:
				ans1 = max(0, x - a[ind]) + max(0, y - s + a[ind])
				if ind != 0:
					ans2 = max(0, y - s + a[ind - 1])
					ans2 += max(0, x - a[ind - 1])
					ans = min(ans1, ans2)
				else:
					ans = ans1
		print(ans)
n = int(input())
a = list(map(int, input().split()))
a.sort()
m = int(input())
b = []
for i in range(m):
	(x, y) = map(int, input().split())
	b.append([x, y])
mgc(a, n, b, m)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
from random import randint as ri
mod = int(1000000000.0) + 7
mod = 998244353
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = 1
for _ in range(t):
	n = ip()
	arr = list(inp())
	arr.sort()
	cur_sum = sum(arr)
	q = ip()
	for i in range(q):
		(x, y) = inp()
		pos = br(arr, x)
		if pos == n:
			ele = arr[n - 1]
			if ele >= x:
				ans1 = 0
			else:
				ans1 = x - ele
			new_sum = cur_sum - ele
		else:
			ele = arr[pos]
			ans1 = 0
			new_sum = cur_sum - ele
		if new_sum >= y:
			pass
		else:
			ans1 += abs(y - new_sum)
		if pos == 0:
			ans = ans1
		else:
			pos -= 1
			ele = arr[pos]
			ans2 = 0
			if ele >= x:
				pass
			else:
				ans2 += x - ele
			new_sum = cur_sum - ele
			if new_sum >= y:
				pass
			else:
				ans2 += y - new_sum
			ans = min(ans1, ans2)
		print(ans)


import sys
from bisect import bisect_left
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
a.sort()
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	i = bisect_left(a, x)
	i = max(0, min(n - 1, i))
	h1 = max(x - a[i - 1], 0) + max(y - (s - a[i - 1]), 0)
	h2 = max(x - a[i], 0) + max(y - (s - a[i]), 0)
	print(min(h1, h2))


from bisect import bisect_right, bisect_left, insort_left
from statistics import mode
from string import ascii_lowercase, ascii_uppercase
from heapq import heapify, heappop, heappush, heappushpop, heapreplace, nlargest, nsmallest, merge
from copy import deepcopy
from random import shuffle
num = int(input())
arr = sorted(map(int, input().split()))
st = set(arr)
total = sum(arr)
mn = min(arr)
mx = max(arr)
cases = int(input())
xy = []
for _ in range(cases):
	(x, y) = map(int, input().split())
	xy.append([x, y])
final = []
for (x, y) in xy:
	if x in st:
		ans = max(0, y + x - total)
	elif x > mx:
		ans = x - mx
		rem = total - mx
		ans += max(0, y - rem)
	elif x < mn:
		ans = 0
		rem = total - mn
		ans += max(0, y - rem)
	else:
		ind = bisect_right(arr, x)
		op1 = arr[ind - 1]
		op2 = arr[ind]
		rem1 = total - op2
		if rem1 >= y:
			ans1 = 0
		else:
			ans1 = y - rem1
		rem2 = total - op1
		ans2 = x - op1
		ans2 += max(0, y - rem2)
		ans = min(ans1, ans2)
	final.append(ans)
for n in final:
	print(n)


import bisect

def slayTheDragon(n, heros, m, dragons):
	heros.sort()
	s = sum(heros)
	for x in dragons:
		strength = x[0]
		power = x[1]
		i = bisect.bisect_left(heros, strength)
		if i == 0:
			first = max(0, power - (s - heros[i]))
			second = float('inf')
		elif i == n:
			first = strength - heros[n - 1] + max(0, power - (s - heros[n - 1]))
			second = float('inf')
		else:
			first = strength - heros[i - 1] + max(0, power - (s - heros[i - 1]))
			second = max(0, power - (s - heros[i]))
		print(min(first, second))
	return
n = int(input())
heros = list(map(int, input().split()))
m = int(input())
dragons = []
for x in range(m):
	dragons.append(list(map(int, input().split())))
slayTheDragon(n, heros, m, dragons)


import math
NO = 'NO'
YES = 'YES'
MOD = 1000000007
ALPH = 'abcdefghijklmnopqrstuvwxyz'

def input_int():
	return int(input())

def input_list():
	return input().split(' ')

def input_list_int():
	return list(map(int, input_list()))

def list_int_to_str(a, sep=' '):
	return sep.join((str(x) for x in a))
global_ans = []

def pr(a):
	global_ans.append(a)

def z_func(s):
	n = len(s)
	z = [0] * n
	l = r = 0
	for i in range(1, n):
		if r >= i:
			z[i] = min(z[i - l], r - i + 1)
		while z[i] + i < n and s[z[i]] == s[z[i] + i]:
			z[i] += 1
		if i + z[i] - 1 > r:
			l = i
			r = i + z[i] - 1
	return z

def is_prime(n):
	d = 2
	while n % d != 0:
		d += 1
	return d == n

def solve():
	n = input_int()
	a = input_list_int()
	a.sort()
	sm = sum(a)
	m = input_int()
	dx = []
	for i in range(m):
		(x, y) = input_list_int()
		dx.append([x, y, i])
	dx.sort(key=lambda x: x[0])
	ans = [0] * m
	gi = 0
	for i in range(m):
		while gi < n - 1 and a[gi] < dx[i][0]:
			gi += 1
		lcl1 = max(dx[i][1] - (sm - a[gi]), 0) + max(dx[i][0] - a[gi], 0)
		lcl2 = math.inf
		if gi > 0:
			lcl2 = max(dx[i][1] - (sm - a[gi - 1]), 0) + max(dx[i][0] - a[gi - 1], 0)
		if lcl2 < lcl1:
			gi -= 1
			ans[dx[i][2]] = lcl2
		else:
			ans[dx[i][2]] = lcl1
	for i in range(m):
		pr(ans[i])
query_count = 1
while query_count:
	query_count -= 1
	solve()
for global_ans_line in global_ans:
	print(global_ans_line)


import math

def binary_search_leftmost(array, find_this_number):
	left = 0
	right = len(array) - 1
	while left < right:
		middle = math.floor((left + right) / 2)
		if check_smaller(array, middle, find_this_number):
			left = middle + 1
		else:
			right = middle
	return left

def check_smaller(array, middle, find_this_number):
	return array[middle] <= find_this_number

def solve(heroes, dragons):
	heroes.sort()
	sum_h = sum(heroes)
	for dragon in dragons:
		(defense, attack) = dragon
		index = binary_search_leftmost(heroes, defense)
		strong_sol = max(0, attack - (sum_h - heroes[index]))
		if heroes[index] < defense:
			strong_sol += defense - heroes[index]
		weak_sol = strong_sol
		if index != 0:
			weak_hero = heroes[index - 1]
			weak_sol = defense - weak_hero
			weak_sol += max(0, attack - (sum_h - weak_hero))
		print(min(weak_sol, strong_sol))
import os
import io
import time
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input().decode().strip())
heroes = [int(x) for x in input().decode().strip().split(' ')]
m = int(input().decode().strip())
dragons = []
for i in range(m):
	(defense, attack) = [int(x) for x in input().decode().strip().split(' ')]
	dragons.append((defense, attack))
a = solve(heroes, dragons)


from bisect import bisect_right
import sys

def solve():
	input = sys.stdin.readline
	n = int(input())
	heros = list(map(int, input().strip().split(' ')))
	m = int(input())
	power_dragon = []
	heros.sort()
	power_heros = 0
	for i in range(n):
		power_heros += int(heros[i])
	for _ in range(m):
		power_dragon = input().split()
		power_dragon_defense = int(power_dragon[0])
		power_dragon_attack = int(power_dragon[1])
		count = 0
		pos = bisect_right(heros, power_dragon_defense)
		if pos == 0:
			count = max(0, power_dragon_attack - power_heros + heros[pos])
		elif pos == len(heros):
			count = power_dragon_defense - heros[pos - 1] + max(0, power_dragon_attack - power_heros + heros[pos - 1])
		else:
			temp1 = power_dragon_defense - heros[pos - 1] + max(0, power_dragon_attack - power_heros + heros[pos - 1])
			temp2 = max(0, power_dragon_attack - power_heros + heros[pos])
			count = min(temp1, temp2)
		print(count)
solve()


from collections import deque
import heapq
from math import sqrt
import operator
from operator import itemgetter
import sys
import copy
inf_var = 0
if inf_var == 1:
	inf = open('input.txt', 'r')
else:
	inf = sys.stdin
input = inf.readline

def read_one_int():
	return int(input().rstrip('\n'))

def read_one_float():
	return float(input().rstrip('\n'))

def read_list_of_ints():
	res = [int(val) for val in input().rstrip('\n').split(' ')]
	return res

def read_str():
	return input().rstrip()

def find_first_ok(strengths, defense):
	res = None
	l = 0
	r = len(strengths) - 1
	while l <= r:
		mid = l + r >> 1
		if strengths[mid] >= defense:
			res = mid
			r = mid - 1
		else:
			l = mid + 1
	return res

def main():
	n = read_one_int()
	strengths = read_list_of_ints()
	strengths.sort()
	str_sum = sum(strengths)
	res = []
	m = read_one_int()
	for _ in range(m):
		(defense, attack) = read_list_of_ints()
		res_1 = 0
		res_2 = 0
		h_ind = find_first_ok(strengths, defense)
		if h_ind is None:
			h_ind = -1
		cur_attack = strengths[h_ind]
		res_1 += max(0, defense - cur_attack)
		res_1 += max(0, attack - (str_sum - cur_attack))
		h_ind -= 1
		if h_ind >= 0:
			cur_attack = strengths[h_ind]
			res_2 += max(0, defense - cur_attack)
			res_2 += max(0, attack - (str_sum - cur_attack))
			res.append(min(res_1, res_2))
		else:
			res.append(res_1)
	print('\n'.join(map(str, res)))
main()


import bisect
import sys
readline = sys.stdin.readline
ii = lambda : int(readline())
mi = lambda : map(int, readline().split())
li = lambda : list(map(int, readline().split()))
INF = 2 ** 63 - 1
N = ii()
A = li()
M = ii()
(X, Y) = ([0] * M, [0] * M)
for i in range(M):
	(X[i], Y[i]) = mi()
A.append(0)
A.sort()
s = sum(A)
A.append(INF)
for i in range(M):
	high = bisect.bisect_left(A, X[i])
	low = max(high - 1, 0)
	if high != N + 1:
		c = max(Y[i] - (s - A[high]), 0)
	else:
		c = INF
	if low != 0:
		d = X[i] - A[low] + max(Y[i] - (s - A[low]), 0)
	else:
		d = INF
	print(min(c, d))


from __future__ import print_function
from math import *
from collections import deque
import os
import sys
from io import BytesIO, IOBase
import bisect

def main():
	pass
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')
mod = 10 ** 9 + 7

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
n = inp()
l = inlt()
l.sort()
m = inp()
s = sum(l)
for i in range(m):
	(a, b) = invr()
	out = 0
	ts = s
	x = bisect.bisect_left(l, a)
	if x == n:
		out += a - l[-1]
		ts -= l[-1]
		out += max(0, b - ts)
	elif x == 0:
		ts -= l[0]
		out += max(0, b - ts)
	else:
		out = max(0, b - (ts - l[x]))
		out1 = a - l[x - 1]
		ts -= l[x - 1]
		out1 += max(0, b - ts)
		print(min(out1, out))
		continue
	print(out)


import sys
input = sys.stdin.readline
from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
a.sort()
m = int(input())
s = sum(a)
ans = [None for _ in range(m)]
for q in range(m):
	(x, y) = map(int, input().split())

	def f(v):
		return max(0, x - a[v]) + max(0, y - (s - a[v])) if 0 <= v and v < n else 1 << 60
	p = bisect_left(a, x)
	ans[q] = min(f(p - 1), f(p))
sys.stdout.write('\n'.join(map(str, ans)) + '\n')


from bisect import bisect_left as bl
import sys
input = sys.stdin.readline
n = int(input())
a = sorted(map(int, input().split()))
total = sum(a)
m = int(input())
for _ in range(m):
	(x, y) = map(int, input().split())
	l = bl(a, x)
	ans = 0
	p = max(l - 1, 0)
	q = min(l, n - 1)
	a1 = x - min(a[p], x)
	r = total - a[p]
	if r < y:
		a1 += y - r
	a2 = x - min(a[q], x)
	r = total - a[q]
	if r < y:
		a2 += y - r
	print(min(a1, a2))


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import defaultdict as dd
import bisect
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdmap = lambda : map(int, stdstr().split())
stdarr = lambda : list(map(int, stdstr().split()))
mod = 1000000007
n = stdint()
a = stdarr()
a.sort()
su = sum(a)
m = stdint()
dragons = []
for i in range(m):
	(x, y) = stdmap()
	pos = bisect.bisect_right(a, x)
	res = float('inf')
	if pos != n:
		f = a[pos]
		fcoins = max(x - f, 0)
		rem = su - a[pos]
		scoins = max(y - rem, 0)
		res = min(res, fcoins + scoins)
	if pos != 0:
		f = a[pos - 1]
		fcoins = max(x - f, 0)
		rem = su - a[pos - 1]
		scoins = max(y - rem, 0)
		res = min(res, fcoins + scoins)
	print(res)


import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict
from io import BytesIO, IOBase
from itertools import permutations
import string

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
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.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, self.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 get_str().split(' ')

def flat_list(arr):
	return [item for subarr in arr for item in subarr]

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):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	return p

def solve_a():
	n = get_int()
	for i in range(1, n + 1):
		r = []
		for j in range(i):
			r.append('(')
		for j in range(i):
			r.append(')')
		for j in range(n - i):
			r.append('()')
		print(''.join(r))
	return

def solve_b():
	(a, b, c, m) = get_ints()
	n = a + b + c
	if m > a + b + c - 3:
		return 'NO'
	if max(a, b, c) > n - n // 2:
		if m < 2 * max(a, b, c) - n - 1:
			return 'NO'
	return 'YES'

def solve_c():
	n = get_int()
	a = get_ints()
	m = get_int()
	a.sort()
	S = sum(a)
	for d in range(m):
		(x, y) = get_ints()
		best = float('inf')
		j = bisect.bisect_right(a, x)
		for i in range(max(0, j - 1), min(n, j + 2)):
			h = a[i]
			curr = max(0, x - h) + max(0, y - (S - h))
			best = min(curr, best)
		print(best)
	return
solve_c()


from __future__ import division, print_function
import math
import sys
import os
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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return int(input())

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

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
import itertools
from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return list(map(str, input().strip()))

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter, deque
import math
import heapq
from heapq import heappop, heappush
import bisect
from math import factorial, inf
from itertools import groupby
from itertools import permutations as comb

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a, b, c):
	print(c, a, b, flush=True)
	n = I()
	return n

def linear_sieve(n):
	is_composite = [False] * n
	prime = []
	for i in range(2, n):
		if not is_composite[i]:
			prime.append(i)
		for j in prime:
			is_composite[i * j] = True
			if i % prime == 0:
				break
	return prime

def dfs(i, p, d):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n // i
	if n > 2:
		l.append(n)
	return l
d = []
primes = []
prim = [0] * (10 ** 5 + 1)

def sieve(n):
	for i in range(n):
		d.append(i)
	for i in range(2, n):
		if d[i] == i:
			prim[i] = 1
			primes.append(i)
		j = 0
		while j < len(primes) and primes[j] <= d[i] and (primes[j] * i < n):
			d[i * primes[j]] = primes[j]
			j += 1

def primeFactors(n):
	factors = []
	while n != 1:
		factors.append(d[n])
		n //= d[n]
	return factors

def func(a):
	b = 1
	res = 0
	for i in range(len(a) - 1, -1, -1):
		res += b * int(a[i])
		b *= 2
	return res
t = 1
for _ in range(t):
	n = inp()
	s = inlt()
	s.sort()
	tmp = sum(s)
	m = inp()
	for i in range(m):
		(x, y) = inlt()
		ans = 1e+20
		if x > s[-1]:
			a = n - 1
			p = 0
			if s[a] < x:
				p = x - s[a]
			if tmp - s[a] < y:
				p += y - tmp + s[a]
			ans = min(ans, p)
		elif x < s[0]:
			a = 0
			p = 0
			if s[a] < x:
				p = x - s[a]
			if tmp - s[a] < y:
				p += y - tmp + s[a]
			ans = min(ans, p)
		else:
			z = min(bisect.bisect_left(s, x), n - 1)
			a = z
			p = 0
			if s[a] < x:
				p = x - s[a]
			if tmp - s[a] < y:
				p += y - tmp + s[a]
			ans = min(ans, p)
			a = max(0, z - 1)
			p = 0
			if s[a] < x:
				p = x - s[a]
			if tmp - s[a] < y:
				p += y - tmp + s[a]
			ans = min(ans, p)
		print(ans)


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from bisect import bisect_left
n = int(input())
a = [int(num) for num in input().split()]
m = int(input())
a.sort()
sum_of_a = sum(a)
for _ in range(m):
	(x, y) = map(int, input().split())
	ind = bisect_left(a, x)
	if ind < n and a[ind] == x:
		print(max(0, y - (sum_of_a - x)))
	elif ind == 0:
		print(max(0, y - (sum_of_a - a[0])))
	elif ind == n:
		print(max(0, y - (sum_of_a - a[-1])) + x - a[-1])
	else:
		print(min(max(0, y - (sum_of_a - a[ind])), max(0, y - (sum_of_a - a[ind - 1])) + x - a[ind - 1]))


import sys
input = sys.stdin.readline

def main():
	from bisect import bisect_left
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	s = sum(a)
	m = int(input())
	for _ in range(m):
		(x, y) = map(int, input().split())
		b = bisect_left(a, x)
		ans1 = 10 ** 20
		if b < n:
			ans1 = y - (s - a[b])
			if ans1 < 0:
				ans1 = 0
		ans2 = 10 ** 20
		if 0 < b:
			ans2 = y - (s - a[b - 1])
			if ans2 < 0:
				ans2 = 0
			ans2 += x - a[b - 1]
		print(min(ans1, ans2))
main()


def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		self.merge_func = merge_func
		self.lg = [0] * (N + 1)
		for i in range(2, N + 1):
			self.lg[i] = self.lg[i >> 1] + 1
		self.pow_2 = [pow(2, i) for i in range(20)]
		self.table = [None] * (self.lg[N] + 1)
		st0 = self.table[0] = [a for a in A]
		b = 1
		for i in range(self.lg[N]):
			st0 = self.table[i + 1] = [self.merge_func(u, v) for (u, v) in zip(st0, st0[b:])]
			b <<= 1

	def query(self, s, t):
		b = t - s + 1
		m = self.lg[b]
		return self.merge_func(self.table[m][s], self.table[m][t - self.pow_2[m] + 1])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

class slope_trick:

	def __init__(self):
		self.L = [10 ** 17]
		self.R = [10 ** 17]
		self.min_f = 0
		self.x_left = 0
		self.x_right = 0

	def add_right(self, a):
		a -= self.x_left
		l0 = -self.L[0]
		self.min_f = self.min_f + max(0, l0 - a)
		if l0 <= a:
			a += self.x_left
			a -= self.x_right
			heappush(self.R, a)
		else:
			heappush(self.L, -a)
			a = -heappop(self.L)
			a += self.x_left
			a -= self.x_right
			heappush(self.R, a)

	def add_left(self, a):
		a -= self.x_right
		r0 = self.R[0]
		self.min_f = self.min_f + max(0, a - r0)
		if a <= r0:
			a += self.x_right
			a -= self.x_left
			heappush(self.L, -a)
		else:
			heappush(self.R, a)
			a = heappop(self.R)
			a += self.x_right
			a -= self.x_left
			heappush(self.L, -a)

	def add_abs(self, a):
		self.add_left(a)
		self.add_right(a)

	def change_min_slide(self, a, b):
		self.x_left += a
		self.x_right += b

	def get_val(self, x):
		L = [-l + self.x_left for l in self.L]
		L.sort()
		R = [r + self.x_right for r in self.R]
		R.sort()
		res = self.min_f
		if 0 < L[-1]:
			L = L[::-1]
			n = len(L)
			for i in range(n):
				c0 = L[i]
				c1 = L[i + 1]
				if c1 <= x <= c0:
					res += (i + 1) * (c0 - x)
					break
				else:
					res += (i + 1) * (c0 - c1)
			return res
		elif L[-1] <= x <= R[0]:
			return res
		else:
			n = len(R)
			for i in range(n):
				c0 = R[i]
				c1 = R[i + 1]
				if c0 <= x <= c1:
					res += (i + 1) * (x - c0)
					break
				else:
					res += (i + 1) * (c1 - c0)
			return res

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			k >>= 1
			self.tree[k] = self.segfunc(self.tree[2 * k], self.tree[2 * k + 1])

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		right = []
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				right.append(self.tree[r - 1])
			l >>= 1
			r >>= 1
		for e in right[::-1]:
			res = self.segfunc(res, e)
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
N = int(input())
A = li()
hero = max(A)
S = sum(A)
A.sort()
for i in range(int(input())):
	(x, y) = mi()
	idx = bisect.bisect_left(A, x)
	tmp = 10 ** 18 + 10 ** 12
	if idx != N:
		tmp = min(tmp, max(0, y - (S - A[idx])))
	if idx != 0:
		cost = x - A[idx - 1]
		tmp_S = S - A[idx - 1]
		tmp = min(tmp, cost + max(0, y - tmp_S))
	print(tmp)


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

def print(a):
	sys.stdout.write(f'{a}\n')
n = int(input())
arr = [int(x) for x in input().split()]
arr.sort()
s = sum(arr)
m = int(input())

def bs_first_greater(arr, start, end, val):
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] > val:
			if mid == start:
				return mid
			elif arr[mid - 1] <= val:
				return mid
			else:
				end = mid - 1
		else:
			start = mid + 1
	return -1
for _ in range(m):
	ans = float('inf')
	t = 0
	(a, d) = [int(x) for x in input().split()]
	index = bs_first_greater(arr, 0, n - 1, a - 1)
	attack = arr[index]
	defence = s - arr[index]
	ans = min(ans, max(0, a - attack) + max(0, d - defence))
	if index != 0:
		index -= 1
		attack = arr[index]
		defence = s - arr[index]
		ans = min(ans, max(0, a - attack) + max(0, d - defence))
	print(ans)


import sys
import bisect
inf = sys.maxsize

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

def get_array():
	return list(map(int, input().split()))
mod = 1000000007
MOD = 998244353

def main():
	n = int(input())
	arr = get_array()
	arr.sort()
	s = sum(arr)
	for tt in range(int(input())):
		(x, y) = get_ints()
		pos = bisect.bisect_left(arr, x)
		ans = float('inf')
		if pos != n:
			ans = min(ans, max(0, y - (s - arr[pos])))
		if pos != 0:
			cost = x - arr[pos - 1]
			tempS = s - arr[pos - 1]
			ans = min(ans, cost + max(0, y - tempS))
		print(ans)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

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

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			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 sys
import bisect
input = sys.stdin.readline
n = int(input())
arr = sorted(list(map(int, input().split())))
q = int(input())
summ = sum(arr)
for _ in range(q):
	(i, j) = map(int, input().split())
	x = bisect.bisect_right(arr, i)
	if x == n:
		sys.stdout.write(str(i - arr[-1] + max(0, j - summ + arr[-1])) + '\n')
	elif x == 0:
		sys.stdout.write(str(max(0, j - summ + arr[0])) + '\n')
	else:
		sys.stdout.write(str(min(i - arr[x - 1] + max(0, j - summ + arr[x - 1]), max(0, j - summ + arr[x]))) + '\n')


import sys
import bisect
import collections
import copy
import itertools
import math
import functools
import operator
from heapq import heappop, heappush
sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7

def I():
	return input().rstrip()

def IS():
	return input().split()

def II():
	return int(input())

def IIS():
	return map(int, input().split())

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

def main():
	num_hero = II()
	pow_hero = LIIS()
	pow_hero.sort()
	s = sum(pow_hero)
	num_dra = II()
	for _ in [0] * num_dra:
		(a, b) = IIS()
		i = bisect.bisect_left(pow_hero, a)
		(out1, out2) = (None, None)
		if i > 0:
			atc = pow_hero[i - 1]
			out1 = a - atc
			out1 += max(b - (s - atc), 0)
		if i < num_hero:
			atc = pow_hero[i]
			out2 = max(b - (s - atc), 0)
		if out1 is None:
			out = out2
		elif out2 is None:
			out = out1
		else:
			out = min(out1, out2)
		print(out)
main()


import sys
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		n = I()
		l = list(In())
		l.sort()
		ans = []
		total = sum(l)
		for i in range(I()):
			(a, b) = In()
			pos = find_gt(l, a)
			ans1 = max(0, a - l[pos]) + max(0, b - total + l[pos])
			ans2 = float('inf')
			if pos - 1 >= 0:
				ans2 = max(0, a - l[pos - 1]) + max(0, b - total + l[pos - 1])
			ans.append(str(min(ans1, ans2)))
		print('\n'.join(ans))
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


import sys
import math
import bisect
from functools import reduce, lru_cache
from collections import Counter, namedtuple, deque, defaultdict
from itertools import groupby, permutations

def getN():
	return int(input())

def getNM():
	return map(int, input().split())

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

def input():
	return sys.stdin.readline().rstrip()
n = getN()
arr = sorted(getList())
m = getN()
sum_def = sum(arr)
for _ in range(m):
	(x, y) = getNM()
	i = bisect.bisect_left(arr, x)
	if i == 0:
		attack = arr[0]
	elif i == len(arr):
		attack = arr[-1]
	else:
		b = arr[i - 1]
		a = arr[i]
		cost1 = max(0, x - a)
		cost1 += max(0, y - (sum_def - a))
		cost2 = max(0, x - b)
		cost2 += max(0, y - (sum_def - b))
		print(min(cost1, cost2))
		continue
	cost = max(0, x - attack)
	cost += max(0, y - (sum_def - attack))
	print(cost)


import sys
import bisect as b
import math
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()
s = sum(a)
m = int(input())
for i in range(m):
	(x, y) = map(int, input().split())
	z = b.bisect_left(a, x)
	ans = 0
	ans += max(0, x - a[z - 1])
	ans += max(0, y - (s - a[z - 1]))
	ans1 = math.inf
	if z != len(a):
		ans1 = max(0, x - a[z])
		ans1 += max(0, y - (s - a[z]))
	print(min(ans, ans1))


from sys import stdin
import bisect
input = stdin.readline
IP = lambda : list(map(int, input().split()))
ip = lambda : input()

def solve(attack):
	global s, hero, x, y
	ret = 0
	defense = s - hero[attack]
	if defense < y:
		ret += y - defense
	if hero[attack] < x:
		ret += x - hero[attack]
	return ret
n = int(ip())
hero = IP() + [10 ** 12 + 1]
hero.sort()
s = sum(hero[:-1])
for i in range(int(ip())):
	(x, y) = IP()
	attack = bisect.bisect_left(hero, x)
	if attack == 0:
		attack += 1
	ret = min(solve(attack), solve(attack - 1))
	print(ret)